Problem overview
The function numberOfSubmatricesWithAllOnes receives a binary matrix mat with m rows and n columns, made of 0s and 1s. It returns how many rectangular submatrices contain only 1s. Rectangles of every size count, including single cells, and two rectangles that cover different cells are different even if they have the same shape.
For mat = [[1,0,1],[1,1,0],[1,1,0]] the answer is 13: six 1x1 rectangles, two 1x2, three 2x1, one 2x2 and one 3x1.
Approach: fix the top and bottom rows, then count along the columns
Checking every rectangle directly means choosing four boundaries and then verifying the cells inside, which is far too slow for a 150 x 150 matrix. The lesson cuts the work down in two moves.
First, fix a vertical slab. Pick a top row upRow and a bottom row downRow. Every rectangle that spans exactly those rows differs only in its left and right columns. A column can belong to such a rectangle only if all its cells between the two rows are 1. Call such a column intact.
Second, count the rectangles from the intact columns. A rectangle in the slab is a block of consecutive intact columns. If you scan the columns left to right and track the length currLength of the current run of intact columns, then a run of length L that ends at this column gives L rectangles with this column as the right edge: widths 1, 2, up to L. Adding currLength at every column therefore counts every rectangle in the slab exactly once, by its right edge.
Moving downRow down one row at a time, the intact columns can only shrink: a 0 in the new row breaks its column for this slab and for every taller slab with the same top. So the column status is updated in place instead of recomputed.
On the example, take the slab of rows 0 to 1. Column 0 has 1 and 1, column 1 has 0 and 1, column 2 has 1 and 0. Only column 0 is intact, so the run is 1 long and the slab contributes 1 rectangle: the 2x1 block in column 0.
Step by step
- Create the counter
matCount, set to 0. It collects every slab's contribution. - Allocate
fullColwithmake, one entry per column. Each entry will say whether that column is still intact in the current slab. - Loop over the top row
upRow, so that every possible top edge is considered. - Reset
fullColto all ones at the start of each top row. A new slab starts with no column disqualified, and leftover zeros from an earlier top row would be wrong. - Loop over the bottom row
downRow, fromupRowto the last row, so the slab grows one row at a time. - Update every column with the new bottom row: when
mat[downRow][col]is 0, set that column's entry to 0. - Start a run counter
currLengthat 0 for the left-to-right scan. - Scan
fullColwith a range loop. An intact column extends the run; a broken one resets it to 0. - Add
currLengthtomatCountat every column, which counts the rectangles ending there. Adding 0 for a broken column is harmless. - Return
matCountafter the loops.
The solution in Go
func numberOfSubmatricesWithAllOnes(mat [][]int) int {
matCount := 0
fullCol := make([]int, len(mat[0]))
for upRow := 0; upRow < len(mat); upRow++ {
for i := 0; i < len(fullCol); i++ {
fullCol[i] = 1
}
for downRow := upRow; downRow < len(mat); downRow++ {
for col := 0; col < len(mat[0]); col++ {
if mat[downRow][col] == 0 {
fullCol[col] = 0
}
}
currLength := 0
for _, col := range fullCol {
if col == 1 {
currLength++
} else {
currLength = 0
}
matCount += currLength
}
}
}
return matCount
}
The Go details worth a closer look:
make([]int, n)creates a slice of lengthnfilled with zeros. That is why the reset loop is needed before first use: the zero value is the opposite of the "intact" marker 1.rangeyields index and value.for _, col := range fullColdiscards the index with the blank identifier_, because Go rejects an unused variable. Herecolis the value (0 or 1), not a column number, unlike thecolin the earlier loop. The two scopes are separate, but it is a naming trap when reading the code.- The reset is a loop. A slice has no fill method, so the code assigns each element.
- Row and column counts.
len(mat)is the number of rows andlen(mat[0])the number of columns. The code assumes at least one row, which the constraints guarantee. - No ternary, no while. The run counter uses a plain
if/else, and all loops arefor.
Complexity
Time: O(m² * n). There are about m²/2 pairs of (upRow, downRow), and each does two passes over the n columns: the update and the scan. With m = n = 150 that is about 11,000 pairs times 150 columns, under two million steps per pass.
Space: O(n). Only fullCol is allocated, one entry per column.
Edge cases and common mistakes
- All zeros.
[[0]]returns 0. - A single 1.
[[1]]returns 1. - One row of ones.
[[1,1,1]]returns 6: three of width 1, two of width 2 and one of width 3. This is the 1 + 2 + 3 pattern the run counter produces. - A full square.
[[1,1],[1,1]]returns 9. - Forgetting the reset of
fullColwhenupRowchanges. A zero from the previous top row would stay and hide rectangles. - Adding
currLengthonly at the end of a run. Every column in a run is the right edge of some rectangles, so the addition belongs inside the loop, after theif/else. - Counting rectangles by shape. The answer counts positions, not distinct sizes, so the six 1x1 rectangles in the example all count.
Testing
[[1,0,1],[1,1,0],[1,1,0]]gives13.[[0,1,1,0],[0,1,1,1],[1,1,1,0]]gives24.[[0]]gives0.[[1,1,1]]gives6.[[1,1],[1,1]]gives9.