Problem overview
The method numberOfSubmatricesWithAllOnes receives a binary matrix mat with m rows and n columns, where every cell is 0 or 1. It returns how many rectangular submatrices contain only ones. Two submatrices are different when their corners differ, even if they cover cells with the same values, and a single cell holding a 1 counts as a 1x1 submatrix.
For [[1,0,1],[1,1,0],[1,1,0]] the answer is 13: six 1x1 submatrices, two 1x2, three 2x1, one 2x2 and one 3x1. For [[0,1,1,0],[0,1,1,1],[1,1,1,0]] the answer is 24. The constraints are at most 150 rows and 150 columns.
Approach: fix the top and bottom rows, then count along the columns
Checking every submatrix one by one would loop over four corners and then scan the cells, which is far too slow even for a 150 by 150 matrix. A better way is to split the work by rows.
Fix a top row upRow and a bottom row downRow. The rows between them, inclusive, form a horizontal slab. A column fits the slab when all its cells in the slab are 1. A submatrix with these exact top and bottom rows is all ones exactly when every one of its columns fits. So the problem inside a slab becomes one-dimensional: count the groups of side-by-side columns that all fit.
In a run of L consecutive fitting columns, the submatrices that end at the last column of the run can have a width of 1, 2, ..., L, giving L of them. So scanning left to right with a running run length currLength, and adding it at every column, counts each submatrix once, by its right edge. A column that doesn't fit resets the run to 0 and adds nothing.
Take the first example. With upRow = 1 and downRow = 1, the slab is the row [1, 1, 0]. The fitting flags are 1, 1, 0, so the run lengths are 1, 2 and 0, which add 3. Those are the two single cells and the 1x2 submatrix spanning both. Adding all the slabs gives 4 for top row 0, 6 for top row 1 and 3 for top row 2, a total of 13.
Step by step
- Start a counter,
matCount, at 0. - Create
fullCol, one entry per column, all 1. Entrycsays whether columncis still all ones in the current slab. - Loop
upRowover every row, so each row is tried as the top edge. - Reset
fullColto all 1 at the start of eachupRow. A new top starts a new slab, and flags left over from the previous top would wrongly remove columns. - Loop
downRowfromupRowto the last row. The slab grows by one row each time. - Loop over the columns and look at the cell in the new bottom row.
- If the cell is 0, set that column's flag to 0. A zero in a column breaks it for this slab, and for every taller slab with the same top, so a flag never turns back on within one
upRow. - Set
currLengthto 0 before scanning the flags. - Scan the flags left to right with
for (const col of fullCol). - If the flag is 1, add one to
currLength. - Otherwise reset
currLengthto 0. - Add
currLengthtomatCountat every column, whichever branch ran. - Return
matCountafter all the loops.
The solution in TypeScript
class Solution {
numberOfSubmatricesWithAllOnes(mat: number[][]): number {
let matCount = 0;
let fullCol: number[] = new Array(mat[0].length).fill(1);
for (let upRow = 0; upRow < mat.length; upRow++) {
for (let i = 0; i < fullCol.length; i++) {
fullCol[i] = 1;
}
for (let downRow = upRow; downRow < mat.length; downRow++) {
for (let col = 0; col < mat[0].length; col++) {
if (!mat[downRow][col]) {
fullCol[col] = 0;
}
}
let currLength = 0;
for (const col of fullCol) {
if (col === 1) {
currLength++;
} else {
currLength = 0;
}
matCount += currLength;
}
}
}
return matCount;
}
}
The TypeScript details worth knowing:
- Truthiness.
!mat[downRow][col]is true when the cell is 0, because 0 is falsy in JavaScript. It is a short way to writemat[downRow][col] === 0. It would also be true forundefined, which is what a read outside the matrix gives. - Two loops named
col. The first is an index declared withletin a classicfor. The second, withfor (const col of fullCol), is a flag value taken straight from the array. Each name exists only inside its own loop, so they don't clash, but they mean different things. - Filling an array.
new Array(mat[0].length).fill(1)creates an array of the right length filled with 1. Thenumber[]annotation exists only for the compiler. for...of. It gives the values of an array, not the indices, which is what the scan needs. Aconstdeclaration is fine here because each pass gets a fresh binding.
Complexity
Time: O(m² · n). There are about m²/2 pairs of upRow and downRow. For each pair, the code does two passes over the n columns, one to update the flags and one to count. The reset adds another n per top row, which is smaller. With 150 rows and columns that is a few million steps.
Space: O(n). Only the fullCol array grows with the input.
Edge cases and common mistakes
- A matrix of zeros.
[[0]]returns 0: the flag drops to 0 and the run never starts. - A single row or column.
[[1,1,1]]returns 6 (three 1x1, two 1x2 and one 1x3).[[1],[1],[1]]also returns 6. - A full matrix.
[[1,1],[1,1]]returns 9: four 1x1, two 1x2, two 2x1 and one 2x2. - Forgetting the reset. Without resetting
fullColfor eachupRow, flags from earlier tops carry over and the count is too low. - Not resetting
currLength. Declare it inside thedownRowloop, so each slab begins with a new run. - Adding only when the run ends. The run length is added at every column. Adding it once per run would count each run as a single submatrix instead of
Lof them.
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]]gives6.[[0]]gives0.[[1,1],[1,1]]gives9.