Count SqAURES [MAXIMAL SQUARE FOLLOW UP]

XXX. Count All Squares

Dynamic Programming

Matrix

Key Points:

• **DP State**:
  • A[i][j] represents count of squares ending at this cell
  • Each cell's value is count of squares it participates in
  • Sum of all values gives total squares
• **Square Formation**:
  • Check three neighbors for square formation
  • Value limited by smallest neighbor
  • Each 1 counts as at least one square

Example:

For matrix:

1 1 1
1 1 1
1 1 1
        

DP array (same as matrix, modified in-place):

1 1 1
1 2 2
1 2 3
        

Sum all values = 14 total squares

Implementation:

Java Solution:

public int countSquares(int[][] A) {
    int res = 0;
    for (int i = 0; i < A.length; ++i) {
        for (int j = 0; j < A[0].length; ++j) {
            if (A[i][j] > 0 && i > 0 && j > 0)    // Not first row/col and is 1
                A[i][j] = min(A[i-1][j-1],        // Check three neighbors
                            A[i-1][j], 
                            A[i][j-1]) + 1;
            res += A[i][j];                        // Add count of squares
        }
    }
    return res;
}

private int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

Python Solution:

def countSquares(self, A: List[List[int]]) -> int:
    res = 0
    for i in range(len(A)):
        for j in range(len(A[0])):
            if A[i][j] and i > 0 and j > 0:   # Not first row/col and is 1
                A[i][j] = min(A[i-1][j-1],    # Check three neighbors
                            A[i-1][j],
                            A[i][j-1]) + 1
            res += A[i][j]                     # Add count of squares
    return res

C++ Solution:

int countSquares(vector>& A) {
    int res = 0;
    for (int i = 0; i < A.size(); ++i) {
        for (int j = 0; j < A[0].size(); ++j) {
            if (A[i][j] && i > 0 && j > 0)     // Not first row/col and is 1
                A[i][j] = min({A[i-1][j-1],    // Check three neighbors
                             A[i-1][j],
                             A[i][j-1]}) + 1;
            res += A[i][j];                     // Add count of squares
        }
    }
    return res;
}

Complexity:

Time Complexity: O(m×n), where m and n are matrix dimensions
Space Complexity: O(1), modifies input matrix

Implementation Notes:

• **In-Place Modification**:
  • Modifies input array to save space
  • Each cell stores count of squares it completes
  • Running sum gives total squares
• **First Row/Column**:
  • Kept as is (single cell squares)
  • No need for special handling
  • Automatically counts as 1 if present