Problem overview
The method numberOfSubmatricesWithAllOnes receives a binary matrix mat with m rows and n columns. It returns how many rectangular submatrices consist only of 1s. A submatrix is any block of consecutive rows and consecutive columns, and a single cell counts as a 1x1 block. Blocks are counted by position, so two blocks of the same shape in different places are different blocks.
For mat = [[1, 0, 1], [1, 1, 0], [1, 1, 0]] the answer is 13: six 1x1 blocks (one per 1), two 1x2, three 2x1, one 2x2, and one 3x1. Both dimensions are at most 150.
Approach: fix a slab of rows, then count along the columns
A rectangle is fixed by its top row, its bottom row, its left column and its right column. Trying every combination is far too slow. The lesson splits the work in two:
- Choose the top row
upRowand the bottom rowdownRow. The rows between them, inclusive, form a slab. - Inside the slab, a column is intact if every cell of that column within the slab is 1. A rectangle that spans exactly this slab is any run of consecutive intact columns.
So the question becomes one-dimensional: given a row of intact (1) and broken (0) columns, how many sub-runs of consecutive intact columns are there? The trick is to count them by right edge. If a run of intact columns has length L at the moment you reach a column, then exactly L rectangles end at that column, one for each possible width 1, 2, ..., L. Adding the current run length at every column totals all of them.
The slab can also be built up cheaply. Keep the top row fixed and move the bottom row down one row at a time. Adding a row can only break columns, never repair them, so one array fullCol is updated incrementally instead of being rebuilt.
On the example, the slab with top row 0 and bottom row 0 is the row [1, 0, 1], with intact columns [1, 0, 1], and contributes 1 + 0 + 1 = 2. Adding row 1, which is [1, 1, 0], breaks column 2 because it holds a 0 there, so the intact columns become [1, 0, 0] and contribute 1. The six slabs give 2, 1, 1, 3, 3 and 3, which sum to 13.
Step by step
- Start the counter.
matCountbegins at 0 and receives every contribution. - Create
fullCol. It has one entry per column, all 1: nothing is broken yet.new Array(n)only makes empty slots, so.fill(1)is chained to set each one. - Loop
upRowfrom the first row to the last. It fixes the top of the rectangles. - Reset
fullColto all 1s at the start of each top row, with a small loop overi. Otherwise, zeros found under an earlier top row would wrongly disqualify columns here. - Loop
downRowfromupRowto the last row. Each value extends the slab by one row. - Loop
colover the columns to fold the new row into the slab. - Break the column on a zero. If
mat[downRow][col]is 0, setfullCol[col]to 0. The state only moves from 1 to 0 as the slab grows taller. - Start a run counter. Declare
currLengthas 0 for each slab. It holds the length of the current run of intact columns. - Scan
fullColwith afor...ofloop. It yields each column's status, 0 or 1, not its index. - Extend the run when the status is 1.
- Reset the run in the
elsebranch, because a broken column ends it. - Add the run length to
matCountafter every column, whether the run grew or reset to 0. A reset adds nothing. - Return
matCountafter all the loops.
The solution in JavaScript
class Solution {
numberOfSubmatricesWithAllOnes(mat) {
let matCount = 0;
let fullCol = 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 (let col of fullCol) {
if (col === 1) {
currLength++;
} else {
currLength = 0;
}
matCount += currLength;
}
}
}
return matCount;
}
}
The JavaScript details worth a look:
new Array(n).fill(1).new Array(3)is an array of length 3 with empty slots, andfill(1)turns it into[1, 1, 1]. Be careful withnew Array(3)when the argument is a single number: it sets the length instead of making an array holding that number.!mat[downRow][col]. The!operator turns a value into its opposite truthiness. 0 is falsy, so!0istrue, and!1isfalse. The test is true exactly for a cell holding 0. It works because the matrix holds only 0 and 1.mat[downRow][col]. A matrix is an array of rows, so the row index goes first.- Two different
colvariables. The firstcolis a numeric index in a classicfor. The second is a value taken fromfullColbyfor...of. Each is scoped to its own loop, so they don't clash, but the second one is a status, not a position. mat[0].lengthreads the column count from the first row, so it assumes the matrix has at least one row. The constraints guarantee that.
Complexity
Time: O(m² * n). There are about m² / 2 (top, bottom) pairs of rows, and for each the code does two passes of n steps: one to update fullCol and one to count. With m and n at most 150 this is about 3.4 million column steps, well within the limit. The reset of fullCol adds O(m * n), which is smaller.
Space: O(n). The only extra memory is the fullCol array.
Edge cases and common mistakes
- A single cell.
[[1]]gives 1 and[[0]]gives 0. - A row of ones.
[[1, 1, 1]]gives 6: three of width 1, two of width 2, one of width 3. The run length goes 1, 2, 3 and the contributions add to 1 + 2 + 3. - A full 2x2.
[[1, 1], [1, 1]]gives 9: four 1x1, two 1x2, two 2x1 and one 2x2. - Not resetting
fullColfor each top row. Columns broken under an earlier top would stay broken. - Not resetting
currLengthon a 0. Runs would join across a broken column and count rectangles that contain a 0. - Counting by area instead of by position. Two 1x1 blocks of ones in different places are two submatrices.
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.[[1, 1], [1, 1]]gives9.[[0]]gives0.