Count Square Submatrices with All Ones

Problem Statement

The task is to determine the number of square submatrices within a given m x n matrix where all elements are either 1 or 0. Specifically, you need to count all possible submatrices where every element is 1. These submatrices can vary in size from a single cell (1x1) to larger squares potentially the size of the entire matrix (if the conditions fit). The challenge involves both identifying these submatrices and ensuring they are square in shape—meaning the height and width are equal.

Examples

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

Approach and Intuition

To solve this problem, let's break down the concept using the provided examples and the constraints that govern the valid solutions:

1. Understanding the Structure of Submatrices:

   • A square submatrix is determined by its smallest dimension since both dimensions must be equal for it to be considered a square. For instance, a 2x2 area within the larger matrix can be a square submatrix if all its entries are 1.

2. Incremental Submatrix Expansion:

   • Starting from each cell that contains a 1, consider it as a potential top-left corner of a square submatrix. Expand this potential square by checking if a larger square that includes this cell as the top-left corner can be formed by verifying if all cells in the intended area are 1.
   • This expansion can continue until you either run out of matrix space or encounter a zero, which disqualifies the current expansion from forming a larger square.

3. Dynamic Programming Approach:

   • Utilize a dynamic programming table where each entry at (i, j) represents the size of the largest square submatrix for which (i, j) is the bottom-right corner.
   • Populate this table by checking the smallest value among the immediate top, left, and top-left neighbors of the cell, which ensures forming a square. This minimizes repeated calculations and inefficiencies found in a naive approach.

4. Summing Up Valid Squares:

   • The sum of all values in the dynamic programming table will give the total number of square submatrices. Each value directly contributes to count different size squares it possibly can be a part of.

By following the above steps, the problem transforms from a mere combinatorial challenge into a structured, step-wise calculation that leverages previous computations for efficient solution finding. The constraints ensure that while the input size may be large, it's manageable within the bounds to apply such an approach effectively.

Solutions

class Solution {
public:
    int totalSquares(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size(), total = 0, last = 0;
        vector<int> dynamicP(cols + 1, 0);
    
        for (int r = 1; r <= rows; r++) {
            for (int c = 1; c <= cols; c++) {
                if (grid[r - 1][c - 1] == 1) {
                    int tempVar = dynamicP[c];
                    dynamicP[c] = 1 + min(last, min(dynamicP[c - 1], dynamicP[c]));
                    last = tempVar;
                    total += dynamicP[c];
                } else {
                    dynamicP[c] = 0;
                }
            }
        }
        return total;
    }
};