Problem overview
The method numberOfSubmatricesWithAllOnes receives a binary matrix mat with m rows and n columns, as an Array[Array[Int]]. It returns how many submatrices contain only ones. A submatrix is a rectangle of neighbouring cells, and rectangles in different positions count separately, even when they have the same size.
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. For [[0, 1, 1, 0], [0, 1, 1, 1], [1, 1, 1, 0]] it is 24. The constraints allow up to 150 rows and 150 columns.
Approach: fix the top and bottom rows
Checking every rectangle of the matrix one by one is far too slow. A better way is to fix the vertical extent first. Pick a top row upRow and a bottom row i, with i at or below upRow. Every rectangle between those two rows is made of whole column segments, so only the columns matter now.
A column is intact for this pair of rows if none of its cells from upRow to i is 0. A rectangle spanning exactly these rows is all ones exactly when all of its columns are intact. So the problem becomes one-dimensional: in a row of intact and broken columns, count the groups of neighbouring intact columns.
A run of L consecutive intact columns holds L * (L + 1) / 2 such groups. The lesson counts them incrementally instead. Walk the columns left to right and track the current run length. At each column, the number of rectangles that use it as their right edge equals the length of the run that ends there: widths 1, 2, up to that length. Adding this run length at every column gives the total for the row pair.
For the first example and the pair upRow = 0, i = 0, the intact columns are [1, 0, 1]. The run lengths are 1, 0, 1, and they add up to 2: the two single cells in that row.
Step by step
- Create the counter
matCountas avarstarting at 0. - Create
fullColwithArray.fill(mat(0).length)(1): one entry per column, where 1 means "still intact". - Loop over the top row
upRowfrom 0 to the last row. - Reset
fullColto all ones at the start of each top row. Breaks from a different top row must not carry over. - Loop over the bottom row
ifromupRowto the last row. - Loop over the columns with
col, to refresh each column's status now that rowijoined the slab. - Break a column when it meets a zero: if
mat(i)(col) == 0, setfullCol(col) = 0. Once a column is broken, it stays broken for every taller slab with the same top row, so the array is never set back to 1 inside the loop fori. - Start a run counter: a
var currLength = 0before scanning the columns. - Scan
fullColfrom left to right. - Extend the run when the entry is 1, by incrementing
currLength. - Reset the run to 0 in the
elsebranch, because a broken column ends it. - Add
currLengthtomatCountat every column. A run of lengthLending here givesLnew rectangles with this column as the right edge. - Return
matCountonce all the loops are done.
The solution in Scala
class Solution {
def numberOfSubmatricesWithAllOnes(mat: Array[Array[Int]]): Int = {
var matCount = 0
var fullCol = Array.fill(mat(0).length)(1)
for (upRow <- 0 until mat.length) {
fullCol = Array.fill(mat(0).length)(1)
for (i <- upRow until mat.length) {
for (col <- 0 until mat(0).length) {
if (mat(i)(col) == 0) {
fullCol(col) = 0
}
}
var currLength = 0
for (col <- fullCol) {
if (col == 1) {
currLength += 1
} else {
currLength = 0
}
matCount += currLength
}
}
}
return matCount
}
}
The Scala details worth a closer look:
Array.fill(k)(1)creates an array ofkones. The first parameter list is the length, the second is the value.- The name
colmeans two things. In the first inner loop,for (col <- 0 until mat(0).length),colis a column index. In the second,for (col <- fullCol)loops over the array's elements, socolis the value 0 or 1 and not an index. The two loops are separate, so there is no clash, but it is easy to misread. mat(i)(col)reads rowi, columncol. Writing to an array element, as infullCol(col) = 0, uses the same parentheses.var fullColis reassigned once per top row. Arrays are mutable, so avaland a loop that refills it would also work; the lesson builds a new array instead. The firstArray.fillbefore the loop is only an initial value that the first iteration replaces.- The return. The lesson finishes with
return matCount. Dropping the keyword and writing justmatCountreturns the same value, which is the more common Scala style.
Complexity
Time: O(m² · n). There are O(m²) pairs of top and bottom rows. For each pair, two passes over the n columns update the statuses and measure the runs. For a 150 by 150 matrix that is around 150 * 150 * 150 / 2 steps, a few million, which runs quickly.
Space: O(n). The fullCol array has one entry per column. Each top row creates a new one, but the old one becomes garbage.
Edge cases and common mistakes
- All zeros.
[[0, 0], [0, 0]]returns0: every run has length 0. - All ones.
[[1, 1], [1, 1]]returns9: four 1x1, two 1x2, two 2x1 and one 2x2. - A single row.
[[1, 1, 1, 1]]returns10, which is 4 + 3 + 2 + 1. A single column[[1], [1], [1]]gives6. - Forgetting to reset
fullCol. A zero in an upper row would disqualify the column for slabs that start below it. The count would be too low. - Resetting
currLengthoutside the scan. The run length must start at 0 for every scan of a new slab, sovar currLength = 0sits inside the loop fori. - Adding to
matCountonly when a run ends. The count would be one per run instead of one per rectangle width. - Using
mat.lengthfor the number of columns. That is the number of rows. The columns aremat(0).length.
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, 0], [0, 0]]gives0.[[1, 1], [1, 1]]gives9.[[1, 1, 1, 1]]gives10.
