Count Square Submatrices with All Ones
Problem Description
Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:
Input:
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:
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] <= 1
Solve it on LeetCode
Approaches
1. Brute Force Solution
Intuition:
The basic idea is to count all possible square submatrices in the matrix that have all ones. The brute force approach involves iterating over every potential square submatrix and checking if it consists entirely of ones.
- Start at every element in the matrix, try expanding it into a square submatrix.
- Check each submatrix to see if every entry is
1. - If a square is valid, increase the count.
This approach checks every possible square matrix, and hence can be quite inefficient for larger matrices.
Code:
- Time Complexity: O(m * n * min(m, n)^2), where m and n are the dimensions of the matrix. We check each submatrix for validity up to the possible maximum size.
- Space Complexity: O(1), since we are using no extra space apart from variables.
2. Dynamic Programming
Intuition:
The dynamic programming approach incrementally builds a solution using previous results. The key insight is recognizing that the size of the square submatrix ending at position (i, j) can be determined by the smallest square ending at positions (i-1, j), (i, j-1), and (i-1, j-1), if (i, j) itself is 1.
- Create a DP table where
dp[i][j]represents the size of the largest square submatrix with all ones ending at(i, j). - Update this table iteratively based on the above relation.
- Sum up all the entries in the DP table to get the total count of squares.
Code:
- Time Complexity: O(m * n), where m and n are the dimensions of the matrix. Each cell is processed once.
- Space Complexity: O(1), since we are using no extra space apart from variables.