Problem overview
The method numberOfSubmatricesWithAllOnes receives a binary matrix mat, an [[Int]] of 0s and 1s with between 1 and 150 rows and columns. It returns how many rectangular submatrices consist only of 1s. Rectangles of every size count, and each position counts separately.
For [[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 by columns
Checking every rectangle cell by cell is too slow. Instead, fix the rectangle's top row upRow and its bottom row i. The rectangle then spans every row from top to bottom, and only its left and right columns are still open.
A column can belong to a rectangle for this pair of rows only if it holds a 1 in every row from upRow to i. Call such a column intact. The array fullCol stores this: fullCol[c] is 1 while column c is intact and 0 once any row of the slab had a 0 there. Moving the bottom row down by one only needs to check the new row. Intact columns stay intact only if the new row has a 1 in them.
Now the all-ones rectangles with these top and bottom rows are exactly the runs of consecutive intact columns: any group of neighbouring intact columns forms one. A run of length L contains L rectangles that end at its last column, with widths 1, 2, ..., L. So scan fullCol from left to right and keep currLength, the length of the run that ends at the current column. Adding currLength at every column counts each rectangle once, by its right edge.
In the first example, the slab with upRow = 1 and bottom row 1 has fullCol = [1, 1, 0]. The run lengths are 1, 2, 0, adding 3 rectangles: two 1x1 and one 1x2. Extending the bottom row to 2 gives the same fullCol and adds 3 more, the two 2x1 and the 2x2.
Step by step
- Declare the total as
var matCount = 0. - Declare
fullCol, avararray with one entry per column ofmat(mat[0].count), every entry set to 1: initially no column is broken. - Loop
upRowover every row,0..<mat.count, so each row serves once as the top edge. - Reset
fullColto all ones at the start of each iteration. A new top row starts a new slab, and zeros left over from the earlier slab would wrongly remove columns. - Loop the bottom row
ifromupRowto the last row. - Loop
colover every column to bringfullColup to date with the new bottom row. - Break a column when it holds a zero. If
mat[i][col]is 0, setfullCol[col]to 0. It never turns back to 1 for taller slabs with the same top, because the zero stays inside them. - Declare
currLengthas avarequal to 0, for the current run of intact columns. - Scan the entries of
fullColwithfor col in fullCol. - Extend the run with
currLength += 1when the entry is 1. - Cut the run in the
elsebranch by settingcurrLengthto 0. - Add
currLengthtomatCountafter the if/else, at every column. A run of length L ending here contributes L rectangles with this column as their right edge. - Return
matCountafter all the loops.
The solution in Swift
class Solution {
func numberOfSubmatricesWithAllOnes(_ mat: [[Int]]) -> Int {
var matCount = 0
var fullCol = [Int](repeating: 1, count: mat[0].count)
for upRow in 0..<mat.count {
fullCol = [Int](repeating: 1, count: mat[0].count)
for i in upRow..<mat.count {
for col in 0..<mat[0].count {
if mat[i][col] == 0 {
fullCol[col] = 0
}
}
var currLength = 0
for col in fullCol {
if col == 1 {
currLength += 1
} else {
currLength = 0
}
matCount += currLength
}
}
}
return matCount
}
}
Swift details worth knowing:
- Two loops that look alike.
for col in 0..<mat[0].countmakescola column index, andfor col in fullColmakescola value from the array, 0 or 1. The names are the same and the meanings differ, and eachcolexists only inside its own loop. - Reassigning an array.
fullCol = [Int](repeating: 1, count: mat[0].count)replaces the whole array. Because arrays are value types, nothing else sees the old contents. The first assignment, at the declaration, is redundant but harmless. - Changing elements.
fullCol[col] = 0compiles becausefullColis avar. Declared withlet, it would be an error. - Half-open ranges.
upRow..<mat.countis non-empty for everyupRowthat the outer loop produces.
Complexity
Let the matrix have R rows and C columns.
Time: O(R² · C). There are about R²/2 pairs of top and bottom rows. Each pair costs O(C): one pass to update fullCol and one to count runs. With 150 rows and columns that is a few million steps.
Space: O(C). Only fullCol and a few integers are stored.
Edge cases and common mistakes
- All zeros.
[[0]]returns 0. - A single 1.
[[1]]returns 1. - One row. A row of three 1s has 3 + 2 + 1 = 6 rectangles, and the run lengths 1, 2, 3 add up to 6.
- All ones. A matrix of 2 by 2 ones gives 9. In general an R by C block of ones has
R(R+1)/2 · C(C+1)/2rectangles. The largest allowed input, 150 by 150, returns 128255625, which anIntholds easily. - Forgetting the reset. Without recreating
fullColfor everyupRow, the zeros of earlier slabs suppress columns that are intact for the new top row, and the count comes out too small. - Counting runs only once. Adding
currLengthonly when a run ends misses the shorter rectangles inside it. The code adds at every column. - Not resetting
currLengthafter a zero. Runs would join across broken columns and count rectangles that contain a 0. - Mixing up the bottom row and the top row. Zeros in rows below
imust not affect the slab, sofullColis updated only with rows fromupRowtoi.
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]]gives1.[[1, 1, 1]]gives6.[[1, 1], [1, 1]]gives9.
