Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:
Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] Output: 15 Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15.
Example 2:
Input: matrix = [ [1,0,1], [1,1,0], [1,1,0] ] Output: 7 Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 + 1 = 7.
Constraints:
1 <= arr.length <= 3001 <= arr[0].length <= 3000 <= arr[i][j] <= 1The dynamic programming approach involves creating a DP array where each element represents the size of the largest square submatrix ending at that element. We'll only consider elements that are 1s, as 0s can't be part of a square of 1s. For each element that is 1, it can be the bottom-right corner of a square submatrix; we consider the minimum of the sizes of squares ending directly above, to the left, and diagonally above and to the left of it, then add 1 to this value. Sum up all the values in the DP array to get the total count of square submatrices.
This C function calculates the number of square submatrices with all ones by using a dynamic programming matrix (dp). For each 1 in the input matrix, it calculates the maximum size of the square submatrix ending at that cell and increments the total count. Bound checks for the first row and column simplify initialization.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n), where m and n are the number of rows and columns in the matrix, respectively.
Space Complexity: O(m * n), due to the auxiliary DP matrix used to store maximum square sizes at each point.
DP 56. Count Square Submatrices with All Ones | DP on Rectangles 🔥 • take U forward • 117,457 views views
Watch 9 more video solutions →Practice Count Square Submatrices with All Ones with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor