Problem overview
The function numberOfSubmatricesWithAllOnes receives a binary matrix mat as an Array<IntArray>. Every cell is 0 or 1. It must return how many rectangular submatrices consist only of ones. Rectangles of every height and width count, and two rectangles are different if their positions or sizes differ.
For [[1, 0, 1], [1, 1, 0], [1, 1, 0]] the answer is 13. There are six 1x1 rectangles (one per 1), two of size 1x2, three of size 2x1, one of size 2x2 and one of size 3x1: 6 + 2 + 3 + 1 + 1 = 13.
Approach: fix the top and bottom rows
Counting all rectangles by their four edges would be slow. The lesson fixes only two of them, the top row upRow and the bottom row i. Together they define a horizontal slab. A rectangle with those exact top and bottom rows can use a column only if that column holds ones in every row of the slab. Call such a column intact.
Within the slab, the problem becomes one-dimensional: take the row of intact and broken columns, and count the runs of consecutive intact columns. A rectangle must sit inside one run, because a broken column in the middle would put a 0 inside it. A run of length L contains L * (L + 1) / 2 different rectangles.
Instead of using that formula, the code adds a running length at every column. A run of length L contributes 1 + 2 + ... + L, which is the same number, because at its k-th column the running length is k and counts the rectangles that end exactly at that column (widths 1 to k).
The status of the columns does not need to be recomputed from scratch for each bottom row. When the slab grows by one row, a column that was intact stays intact only if the new row has a 1 there. Columns only ever switch from intact to broken, so a single array, fullCol, can be updated in place.
Step by step
- Declare
matCountas avarstarting at 0: the answer being accumulated. - Create
fullCol, anIntArraywith one entry per column, andfillit with 1. A 1 means "no zero seen in this column of the slab". - Loop over
upRow, every possible top row. - Refill
fullColwith 1 at the start of each top row. Without this, zeros from an earlier slab would wrongly disqualify columns. - Loop over
ifromupRowto the last row, so the slab grows downwards one row at a time. - Loop over the columns to include the new row.
- Break columns that hit a zero. If
mat[i][col]is 0, setfullCol[col]to 0. - Start
currLengthat 0 to measure the current run of intact columns. - Scan
fullColfrom left to right. IncreasecurrLengthon a 1 and reset it to 0 on anything else. - Add
currLengthtomatCountat every column, as described above. - Return
matCountafter the loops.
The solution in Kotlin
class Solution {
fun numberOfSubmatricesWithAllOnes(mat: Array<IntArray>): Int {
var matCount = 0
val fullCol = IntArray(mat[0].size)
fullCol.fill(1)
for (upRow in 0 until mat.size) {
fullCol.fill(1)
for (i in upRow until mat.size) {
for (col in 0 until mat[0].size) {
if (mat[i][col] == 0) {
fullCol[col] = 0
}
}
var currLength = 0
for (col in fullCol) {
if (col == 1) {
currLength++
} else {
currLength = 0
}
matCount += currLength
}
}
}
return matCount
}
}
Tracing the example
With upRow = 0, row 0 is [1, 0, 1], so fullCol becomes [1, 0, 1]. The scan adds 1 for column 0, nothing for column 1 and 1 for column 2. Rows 1 and 2 both have a 0 in column 2, so fullCol becomes [1, 0, 0] and each adds 1. The top row 0 contributes 4 in total. Top row 1 adds 3 + 3 = 6, because its slabs have intact columns [1, 1, 0], giving runs of 1 and 2 (1 + 2 = 3). Top row 2 adds 3. The total is 4 + 6 + 3 = 13.
Kotlin details worth knowing:
IntArray.fill(1)overwrites every element in place. The array stays the same object, sovalis enough: the variable is never reassigned, only the contents change.- Two different
colvariables. Infor (col in 0 until mat[0].size),colis an index. Infor (col in fullCol),colis an element value, 0 or 1. They live in separate loops, so they don't clash. mat.sizeis the row count andmat[0].sizethe column count. Becausemat[0]is read first, an emptymatwould throw an exception; the lesson guarantees at least one row and one column.
Complexity
Let the matrix have R rows and C columns.
Time: O(R² · C). The loops over upRow and i visit about R²/2 slabs, and each slab costs two O(C) passes. Counting every rectangle by checking all four edges and every cell would be far slower.
Space: O(C). The only extra memory is fullCol.
Edge cases and common mistakes
- All zeros.
[[0]]returns 0:fullColbecomes[0]and the run length stays 0. - All ones. A 2x3 matrix of ones returns 18: it has 3 choices of row range (two single rows and both rows together) and 6 choices of column range, and 3 times 6 is 18.
- Forgetting the reset of
fullCol. A zero from a previous top row would remove columns from slabs that don't contain it. - Adding only at the end of a run. Adding
currLengthonce, at the end of each run, counts the widest rectangles and misses all the narrower ones. - Not resetting
currLengthon a broken column. Rectangles would then span a column with a zero. - Using the wrong count for columns.
mat.sizeis the row count. Looping over the columns up tomat.sizereads the wrong range on a non-square matrix.
Testing
[[1, 0, 1], [1, 1, 0], [1, 1, 0]]gives13.[[0, 1, 1, 0], [0, 1, 1, 1], [1, 1, 1, 0]]gives24.[[1, 1, 1], [1, 1, 1]]gives18.[[0]]gives0.