1277. Count Square Submatrices with All Ones - Detailed Explanation

Problem Statement

Given an m × n binary matrix matrix, where each element is either 0 or 1, return the total number of square submatrices that contain only 1’s. A square submatrix of size k is defined by selecting a top‑left corner (r, c) and taking the k contiguous rows and k contiguous columns starting at (r, c).

Input

• matrix: a list of m rows, each containing n integers (0 or 1)

Output

• An integer representing the count of all square submatrices comprised entirely of 1’s

Examples
Example 1
Input

matrix = [
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]

Output

15

Explanation
Ten 1×1 squares, four 2×2 squares, and one 3×3 square

Example 2
Input

matrix = [
  [1,0,1],
  [1,1,0],
  [1,1,0]
]

Output

7

Explanation
Six 1×1 squares and one 2×2 square

Example 3
Input

matrix = [[1]]

Output

1

Constraints

• 1 ≤ m, n ≤ 300
• matrix[i][j] is either 0 or 1

Hints

1. A k×k square ending at cell (i,j) must have all four corners and all interior cells be 1
2. Brute force: try every top‑left corner and every possible size, check all cells
3. Observe overlap: squares ending at (i,j) build on squares ending at its top, left and top‑left neighbors

Approach 1: Brute Force

Explanation

For each cell as the bottom‑right corner, try every possible square size up to the matrix bounds. For each candidate square, scan all its cells to verify they’re 1.

Algorithm

1. Initialize count = 0
2. For i in [0…m−1], for j in [0…n−1]:
   1. For k from 1 to min(i+1, j+1):
      • Check all cells in the k×k submatrix with bottom‑right (i,j)
      • If all are 1, increment count, else break inner loop (larger k impossible)

Step‑by‑Step Walkthrough

Consider

1 1 0
1 1 1
0 1 1

• At (1,1) with value 1, k=1 is valid ⇒ count+=1
• Try k=2: submatrix [[1,1],[1,1]] is all 1 ⇒ count+=1
• Try k=3: out of bounds in rows or cols ⇒ stop

Visual Example

Matrix                  Checking k=2 at (1,1)
1 1 0                   [1 1]
1 1 1      →  submatrix [1 1]
0 1 1

Approach 2: Dynamic Programming

Explanation

Let dp[i][j] be the side length of the largest square ending at (i,j). If matrix[i][j]==1, dp[i][j] = 1 + min(dp[i−1][j], dp[i][j−1], dp[i−1][j−1]); otherwise dp[i][j] = 0. Each dp[i][j] contributes exactly dp[i][j] squares.

DP Formulation

if matrix[i][j] == 1:
  if i==0 or j==0:
    dp[i][j] = 1
  else:
    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
else:
  dp[i][j] = 0

Algorithm

1. Create dp array of same size, initialize all zeros
2. total = 0
3. Loop i=0…m−1, j=0…n−1: compute dp[i][j] as above, then total += dp[i][j]
4. Return total

Step‑by‑Step Walkthrough

For

0 1 1 1
1 1 1 1
0 1 1 1

dp builds as

0 1 1 1
1 1 2 2
0 1 2 3

Sum of all entries = 15

Visual Example

Initial dp row (i=0 or j=0) simply mirror matrix’s 1’s
Then at (1,2): min(dp[0][2],dp[1][1],dp[0][1]) +1 = min(1,1,1)+1 = 2

Complexity Analysis

Time: O(m × n) because each cell does O(1) work
Space: O(m × n) for dp, or O(n) if you optimize to a rolling array

Code Solutions

Python