Problem Description

You are given a binary matrix mat of size m x n containing only 0s and 1s. Your task is to count the total number of submatrices that contain only 1s.

A submatrix is any contiguous rectangular portion of the original matrix. It can be defined by selecting a top-left corner (r1, c1) and a bottom-right corner (r2, c2) where r1 ≤ r2 and c1 ≤ c2. The submatrix includes all elements mat[i][j] where r1 ≤ i ≤ r2 and c1 ≤ j ≤ c2.

For example, if you have a 3x3 matrix:

1 1 1
1 1 1
1 1 1

The number of submatrices with all 1s includes:

• 9 submatrices of size 1x1
• 6 submatrices of size 1x2
• 3 submatrices of size 1x3
• 6 submatrices of size 2x1
• 4 submatrices of size 2x2
• 2 submatrices of size 2x3
• 3 submatrices of size 3x1
• 2 submatrices of size 3x2
• 1 submatrix of size 3x3

The total would be 36 submatrices.

The solution uses a preprocessing step to calculate g[i][j], which represents the maximum width of consecutive 1s extending left from position (i, j). Then for each position (i, j), it considers all possible submatrices with (i, j) as the bottom-right corner by iterating upward through rows and tracking the minimum width available at each height.

Intuition

The key insight is to fix the bottom-right corner of potential submatrices and count how many valid submatrices end at each position.

Consider any position (i, j) in the matrix. If we want to count all submatrices that have (i, j) as their bottom-right corner, we need to consider all possible top-left corners that form valid all-1 submatrices with this point.

The challenge is efficiently counting these submatrices. A naive approach would check every possible submatrix, but this would be too slow. Instead, we can make a crucial observation: for any column j, as we move upward from row i, the maximum width of valid submatrices is constrained by the minimum width seen so far.

To understand this better, imagine we're at position (i, j) and looking upward. For row i, we might have 5 consecutive 1s extending to the left. For row i-1, we might have only 3 consecutive 1s. This means any submatrix that includes both rows can have a maximum width of 3, not 5.

This leads us to precompute g[i][j] - the number of consecutive 1s extending left from position (i, j) in each row. This preprocessing allows us to quickly determine the maximum width available at any position.

Then, for each position (i, j), we iterate upward from row i to row 0. As we include each new row k, we update our running minimum width (col = min(col, g[k][j])). This minimum represents the maximum width of submatrices that span from row k to row i and end at column j. We add this value to our answer because it represents the number of valid submatrices with heights from (k, j) to (i, j) and varying widths from 1 to col.

Learn more about Stack, Dynamic Programming and Monotonic Stack patterns.

Solution Approach

The solution consists of two main phases: preprocessing and counting.

Phase 1: Preprocessing - Building the Width Array g

First, we create a 2D array g with the same dimensions as the input matrix. For each position (i, j), g[i][j] stores the maximum width of consecutive 1s extending from position (i, j) to the left in row i.

for i in range(m):
    for j in range(n):
        if mat[i][j]:
            g[i][j] = 1 if j == 0 else 1 + g[i][j - 1]

For each cell:

• If mat[i][j] = 0, then g[i][j] = 0 (remains initialized value)
• If mat[i][j] = 1 and it's the first column (j = 0), then g[i][j] = 1
• If mat[i][j] = 1 and it's not the first column, then g[i][j] = 1 + g[i][j-1], extending the consecutive 1s count from the left

Phase 2: Counting Submatrices

For each position (i, j) as a potential bottom-right corner:

for i in range(m):
    for j in range(n):
        col = inf
        for k in range(i, -1, -1):
            col = min(col, g[k][j])
            ans += col

We iterate upward from row i to row 0 (represented by variable k). As we include each row:

1. Update col = min(col, g[k][j]) - this maintains the minimum width available from row k to row i
2. Add col to the answer - this represents all submatrices with:
   • Bottom-right corner at (i, j)
   • Top row at k
   • Bottom row at i
   • Width ranging from 1 to col

The reason we add col directly is that if the minimum width is col, we can form col different submatrices with this height configuration - one for each possible width from 1 to col.

Time Complexity: O(m²n) where we have O(mn) for preprocessing and O(m²n) for the counting phase.

Space Complexity: O(mn) for the auxiliary array g.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider the matrix:

mat = [
  [1, 1, 0],
  [1, 1, 1],
  [0, 1, 1]
]

Phase 1: Build the width array g

We calculate g[i][j] = number of consecutive 1s extending left from position (i,j):

Row 0:

• g[0][0] = 1 (mat[0][0]=1, first column)
• g[0][1] = 2 (mat[0][1]=1, extends from g[0][0])
• g[0][2] = 0 (mat[0][2]=0)

Row 1:

• g[1][0] = 1 (mat[1][0]=1, first column)
• g[1][1] = 2 (mat[1][1]=1, extends from g[1][0])
• g[1][2] = 3 (mat[1][2]=1, extends from g[1][1])

Row 2:

• g[2][0] = 0 (mat[2][0]=0)
• g[2][1] = 1 (mat[2][1]=1, but g[2][0]=0 so starts fresh)
• g[2][2] = 2 (mat[2][2]=1, extends from g[2][1])

Result:

g = [
  [1, 2, 0],
  [1, 2, 3],
  [0, 1, 2]
]

Phase 2: Count submatrices

Now we fix each position as bottom-right corner and count valid submatrices:

Position (0,0): g[0][0] = 1

• k=0: col = min(∞, 1) = 1, add 1
• Total: 1

Position (0,1): g[0][1] = 2

• k=0: col = min(∞, 2) = 2, add 2
• Total: 2

Position (0,2): g[0][2] = 0

• k=0: col = min(∞, 0) = 0, add 0
• Total: 0

Position (1,0): g[1][0] = 1

• k=1: col = min(∞, 1) = 1, add 1
• k=0: col = min(1, 1) = 1, add 1
• Total: 2

Position (1,1): g[1][1] = 2

• k=1: col = min(∞, 2) = 2, add 2 (covers 2 submatrices of height 1)
• k=0: col = min(2, 2) = 2, add 2 (covers 2 submatrices of height 2)
• Total: 4

Position (1,2): g[1][2] = 3

• k=1: col = min(∞, 3) = 3, add 3
• k=0: col = min(3, 0) = 0, add 0
• Total: 3

Position (2,0): g[2][0] = 0

• k=2: col = min(∞, 0) = 0, add 0
• k=1: col = min(0, 1) = 0, add 0
• k=0: col = min(0, 1) = 0, add 0
• Total: 0

Position (2,1): g[2][1] = 1

• k=2: col = min(∞, 1) = 1, add 1
• k=1: col = min(1, 2) = 1, add 1
• k=0: col = min(1, 2) = 1, add 1
• Total: 3

Position (2,2): g[2][2] = 2

• k=2: col = min(∞, 2) = 2, add 2
• k=1: col = min(2, 3) = 2, add 2
• k=0: col = min(2, 0) = 0, add 0
• Total: 4

Final Answer: 1 + 2 + 0 + 2 + 4 + 3 + 0 + 3 + 4 = 19

The 19 submatrices consist of various rectangles with all 1s, including single cells like [1,1], horizontal strips like the two cells at positions (0,0)-(0,1), vertical strips, and larger rectangles like the 2x2 square at positions (0,0)-(1,1).

Solution Implementation

Time and Space Complexity

Time Complexity: O(m² × n)

The algorithm consists of two main parts:

1. First nested loop (preprocessing): Iterates through all m × n elements to compute the consecutive 1s extending left from each position. This takes O(m × n) time.

2. Second triple nested loop (counting submatrices):

   • The outer two loops iterate through all positions (i, j) in the matrix: O(m × n) iterations
   • For each position (i, j), the innermost loop iterates from row i up to row 0, which is at most m iterations
   • Inside the innermost loop, we perform constant time operations (min comparison and addition)
   • Total: O(m × n × m) = O(m² × n)

Since O(m × n) + O(m² × n) = O(m² × n), the overall time complexity is O(m² × n).

Space Complexity: O(m × n)

The algorithm uses:

• A 2D array g of size m × n to store the lengths of consecutive 1s extending left
• A few constant space variables (ans, col, loop counters)

Therefore, the space complexity is O(m × n) where m and n are the number of rows and columns of the matrix, respectively.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Width Calculation Direction

A common mistake is calculating the consecutive 1s count in the wrong direction. Some might try to count consecutive 1s extending to the right instead of to the left, which breaks the algorithm's logic when using each position as a bottom-right corner.

Incorrect approach:

# Wrong: counting to the right
for i in range(rows):
    for j in range(cols - 1, -1, -1):
        if mat[i][j] == 1:
            consecutive_ones[i][j] = 1 if j == cols - 1 else consecutive_ones[i][j + 1] + 1

Correct approach:

# Correct: counting to the left
for i in range(rows):
    for j in range(cols):
        if mat[i][j] == 1:
            consecutive_ones[i][j] = 1 if j == 0 else consecutive_ones[i][j - 1] + 1

2. Misunderstanding the Minimum Width Logic

Another pitfall is not properly maintaining the minimum width constraint when extending the submatrix upward. Each row added might have a different maximum width of consecutive 1s, and the valid submatrix width is constrained by the minimum across all included rows.

Incorrect approach:

for i in range(rows):
    for j in range(cols):
        for k in range(i, -1, -1):
            # Wrong: directly using the width at current row
            total_submatrices += consecutive_ones[k][j]

Correct approach:

for i in range(rows):
    for j in range(cols):
        min_width = float('inf')
        for k in range(i, -1, -1):
            # Correct: maintaining the minimum width across all rows
            min_width = min(min_width, consecutive_ones[k][j])
            total_submatrices += min_width

3. Off-by-One Errors in Loop Boundaries

When iterating through possible top rows (variable k), it's crucial to include row 0. Using range(i, 0, -1) instead of range(i, -1, -1) would miss all submatrices that extend to the first row.

Incorrect approach:

for k in range(i, 0, -1):  # Misses row 0
    min_width = min(min_width, consecutive_ones[k][j])
    total_submatrices += min_width

Correct approach:

for k in range(i, -1, -1):  # Includes row 0
    min_width = min(min_width, consecutive_ones[k][j])
    total_submatrices += min_width

4. Not Handling Edge Cases Properly

Failing to handle the first column correctly when building the consecutive ones array can lead to index out of bounds errors.

Incorrect approach:

for i in range(rows):
    for j in range(cols):
        if mat[i][j] == 1:
            # Wrong: always accessing j-1, causes error when j=0
            consecutive_ones[i][j] = 1 + consecutive_ones[i][j - 1]

Correct approach:

for i in range(rows):
    for j in range(cols):
        if mat[i][j] == 1:
            # Correct: special handling for j=0
            consecutive_ones[i][j] = 1 if j == 0 else 1 + consecutive_ones[i][j - 1]