🌱 Keegan's Digital Garden

1277. Count Square Submatrices with All Ones

3 min read

📝 Problem Details

💭What Were My Initial Thoughts?

Naïve approach:
- Count all individual 1s.
- Count all 2×2 matrices.
- Count all 3×3 matrices.
- Continue until reaching the largest possible square.

Issues with this approach:
- Repeatedly scanning the matrix for different square sizes is inefficient.
- This leads to a worst-case time complexity of O(n³) in brute force.
- There must be a way to break this into smaller subproblems and build up the solution.

🤔What Did I Struggle With?

- Initially, I was unsure whether to approach this problem top-down (starting from the largest possible square) or bottom-up.
- Understanding how to transition from smaller subproblems to larger squares using DP.
- Determining how to store and use previous results efficiently.
- Finding a space-optimized way to store the DP values instead of using a full 2D matrix.

💡 Explanation of Solution

Step 1: Define the DP State
- Let `dp[i][j]` represent the size of the largest square that ends at (i, j)
- The final answer will be the sum of all `dp[i][j]` values.


Step 2: Base Case
- If `matrix[i][j] == 1` and it's in the **first row (i == 0) or first column (j == 0)**, then `dp[i][j] = 1` (it can only form a 1×1 square).
- Otherwise, use the DP formula:
	dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
	

Step 3: Transition
- If a `1` is found at `(i, j)`, check its top, left, and top-left diagonal neighbors:
  - If all three are part of a square, extend it.
  - Otherwise, `dp[i][j]` can only be `1`.


Step 4: Optimizing Space
- Instead of using a full `dp` matrix (`O(m × n)` space), we:
  - Maintain **only one row** (`O(n) space`).
  - Keep a `prev` variable to store `dp[i-1][j-1]` (top-left diagonal).


Step 5: Summing the Squares
- The sum of all `dp[i][j]` values gives the final count of square submatrices.

⌛ Complexity Analysis

Time Complexity: O(m * n)
	- each cell is visited once, making it linear with respect to the matrix size 

Space Complexity: O(n)
	- instead of storing a full 2D table, we only store

💻 Implementation of Solution

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        
        vector<int> prev(cols, 0);  // Stores the previous row's DP values
        vector<int> curr(cols, 0);  // Stores the current row's DP values
        int totalSquares = 0;
 
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 1) {
                    if (i == 0 || j == 0) {
                        curr[j] = 1;  // Base case: First row or first column
                    } else {
                        curr[j] = min({prev[j], curr[j-1], prev[j-1]}) + 1;
                    }
                    totalSquares += curr[j];
                } else {
                    curr[j] = 0;  // Reset for next row iteration
                }
            }
            prev = curr;  // Move current row to previous row for next iteration
        }
        
        return totalSquares;
    }
 
};

Graph View