Scale Engineer

Count Square Submatrices with All Ones

Med
#1191Time: O(m * n * min(m, n)^3). We have loops for rows (m), columns (n), and side length (min(m,n)). Inside, we check an s x s square, which takes O(s^2) time. A slightly better implementation checks only the new border, leading to O(m * n * min(m, n)^2). In either case, it's a high-degree polynomial complexity.Space: O(1) extra space, as we are only using a few variables to keep track of the count and loop indices.1 company
Patterns
Dynamic Programming
Data structures
ArrayMatrix
Companies
Tinkoff

Prompt

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 <= 300
  • 1 <= arr[0].length <= 300
  • 0 <= arr[i][j] <= 1

Approaches

4 approaches with complexity analysis and trade-offs.

The brute-force approach is the most straightforward way to solve the problem. It involves systematically checking every possible submatrix to see if it's a square composed entirely of ones. We can iterate through every cell of the matrix, considering it as the top-left corner of a potential square. From each top-left corner, we then try to form squares of increasing side lengths (1x1, 2x2, 3x3, etc.) and for each size, we verify if all its elements are ones. If they are, we increment our total count.

Algorithm

  1. Initialize a counter count to 0.
  2. Get the dimensions of the matrix, m (rows) and n (columns).
  3. Iterate through each cell (r, c) from (0, 0) to (m-1, n-1). This cell will serve as the potential top-left corner of a square.
  4. For each cell (r, c), if matrix[r][c] is 1, start checking for squares of increasing size s starting from s=1.
  5. The maximum possible side length s for a square starting at (r, c) is min(m-r, n-c).
  6. For each size s, check if the s x s submatrix starting at (r, c) is composed entirely of ones.
    • This involves a nested loop from i = r to r + s - 1 and j = c to c + s - 1.
    • If any element matrix[i][j] is 0, then it's not a valid square of ones. We can stop checking for larger sizes from this (r, c) and break the loop over s.
  7. If the s x s submatrix is all ones, increment the count.
  8. After all iterations, return the total count.

Walkthrough

This method iterates through all possible top-left corners (r, c) of a square. For each corner, it then iterates through all possible side lengths s. For each combination of (r, c, s), it checks if the corresponding s x s submatrix contains only ones. A helper function or nested loops can perform this check. If the check passes, a counter is incremented. To add a small optimization, if a square of size s starting at (r, c) is found to not be all ones, we know that no square of size s+1 or larger starting at the same corner can be all ones, so we can stop checking for larger sizes from that corner.

class Solution {    public int countSquares(int[][] matrix) {        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {            return 0;        }        int m = matrix.length;        int n = matrix[0].length;        int count = 0;         for (int r = 0; r < m; r++) {            for (int c = 0; c < n; c++) {                if (matrix[r][c] == 1) {                    int maxSide = Math.min(m - r, n - c);                    for (int s = 1; s <= maxSide; s++) {                        if (isAllOnes(matrix, r, c, s)) {                            count++;                        } else {                            // If a square of size s is not all ones,                            // no larger square from this corner can be all ones.                            break;                        }                    }                }            }        }        return count;    }     private boolean isAllOnes(int[][] matrix, int r, int c, int s) {        for (int i = r; i < r + s; i++) {            for (int j = c; j < c + s; j++) {                if (matrix[i][j] == 0) {                    return false;                }            }        }        return true;    }}

Complexity

Time

O(m * n * min(m, n)^3). We have loops for rows (m), columns (n), and side length (min(m,n)). Inside, we check an s x s square, which takes O(s^2) time. A slightly better implementation checks only the new border, leading to O(m * n * min(m, n)^2). In either case, it's a high-degree polynomial complexity.

Space

O(1) extra space, as we are only using a few variables to keep track of the count and loop indices.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Requires no extra space (O(1) space complexity).

Cons

  • Extremely inefficient due to multiple nested loops.

  • The time complexity makes it infeasible for the given constraints, likely resulting in a 'Time Limit Exceeded' error.

Solutions

class Solution {public  int countSquares(int[][] matrix) {    int m = matrix.length;    int n = matrix[0].length;    int[][] f = new int[m][n];    int ans = 0;    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        if (matrix[i][j] == 0) {          continue;        }        if (i == 0 || j == 0) {          f[i][j] = 1;        } else {          f[i][j] =              Math.min(f[i - 1][j - 1], Math.min(f[i - 1][j], f[i][j - 1])) + 1;        }        ans += f[i][j];      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem