Problem overview
The function number_of_submatrices_with_all_ones receives a binary matrix mat (a Vec<Vec<i32>> with m rows and n columns, every cell 0 or 1) and returns how many rectangular submatrices consist only of ones. Rectangles of every size count, and two rectangles at different positions are different even when they have the same shape.
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.
Approach: fix the top and bottom rows
A rectangle is chosen by a top row, a bottom row and a range of columns. Fix the top row up_row and the bottom row down_row. That defines a horizontal slab. A column can belong to a rectangle in this slab only if it has a 1 in every row of the slab. Mark such columns as intact.
Inside the slab, a rectangle of ones is just a range of consecutive intact columns. Counting those ranges is easy: a run of L intact columns contains L ranges ending at its last column, L - 1 ending one column earlier, and so on, for a total of L (L + 1) / 2. The lesson counts them as it scans: at each column, the run that currently ends there has length curr_length, and exactly that many new rectangles have this column as their right edge, with widths 1 to curr_length. Add curr_length at every column, and each rectangle is counted once, at its right edge.
The intact marks don't need recomputing for each slab. For a fixed top row, extending the bottom row by one only adds one more row of constraints: a column stays intact only if the new row also has a 1 in it. So full_col is reset when the top row changes and updated by one row at a time as the bottom row moves down.
For the first example, take up_row = 1 and down_row = 2. The two rows are [1, 1, 0], so the intact marks are [1, 1, 0]. The running lengths are 1, 2 and 0, which add 3 rectangles to the count. These are the two 2x1 rectangles (one per intact column) and the 2x2 rectangle across both columns.
Step by step
- Declare
mat_countas a mutable counter starting at 0. - Declare
full_colas a mutable vector with one entry per column, all 1. Entrycsays whether columncis still intact in the current slab. - Loop over
up_rowfrom 0 to the last row, so that every top edge is tried. - Reset
full_colto all 1s at the start of each top row. A new slab starts with no column ruled out, and stale zeros from the previous top row would be wrong. - Loop over
down_rowfromup_rowto the last row, so the bottom edge grows one row at a time. - Loop over the columns to refresh them for the row that just joined the slab.
- Zero the entry of any column where
mat[down_row][col]is 0. A column with a zero in the slab can't be part of an all-ones rectangle of this height. Once zeroed, it stays zero for taller slabs with the same top. - Declare
curr_length, a mutable counter at 0 for the current run of intact columns, then scanfull_colfrom left to right. - Write the scan as
for &col in &full_col. The borrow leaves the vector usable for the next slab, and the&in the pattern copies each entry out of its reference. - Extend or reset the run: when
colis 1, incrementcurr_length. Otherwise set it to 0. - Add
curr_lengthtomat_countat every column, whether the column is intact or not. When it isn't,curr_lengthis 0 and nothing is added. - Return
mat_countafter the loops, with no semicolon.
The solution in Rust
impl Solution {
fn number_of_submatrices_with_all_ones(mat: Vec<Vec<i32>>) -> i32 {
let mut mat_count = 0;
let mut full_col = vec![1; mat[0].len()];
for up_row in 0..mat.len() {
for i in 0..full_col.len() {
full_col[i] = 1;
}
for down_row in up_row..mat.len() {
for col in 0..mat[0].len() {
if mat[down_row][col] == 0 {
full_col[col] = 0;
}
}
let mut curr_length = 0;
for &col in &full_col {
if col == 1 {
curr_length += 1;
} else {
curr_length = 0;
}
mat_count += curr_length;
}
}
}
mat_count
}
}
The Rust details worth a closer look:
- Type inference. No type is written for
mat_count,full_colorcurr_length. Becausecol == 1compares with the matrix'si32values andmat_countis returned as ani32, the compiler infersi32for all of them. vec![1; mat[0].len()]. The macro makes a vector of copies of 1, one for each column. The rowmat[0]gives the column count, so the code assumes at least one row.- Iterating by reference.
for &col in &full_colborrows the vector instead of consuming it. A plainfor col in full_colwould move it, and the next slab couldn't use it. - Mutating while looping over indices. The refresh loop uses
for col in 0..mat[0].len()and writesfull_col[col], so it never holds a borrow offull_colwhile changing it. - Overflow. The count can reach about
(m (m + 1) / 2) · (n (n + 1) / 2). For the largest allowed size, 150 by 150 with all ones, that is 128,255,625, which fits comfortably in ani32.
Complexity
Time: O(m² n). There are about m² / 2 pairs of rows, and each pair does O(n) work to refresh the columns and scan them. Recounting every rectangle separately would cost far more.
Space: O(n). Only full_col grows with the input, and it holds one entry per column.
Edge cases and common mistakes
- A single cell.
[[0]]gives 0, and[[1]]gives 1. - One row.
[[1, 1, 1]]gives 6, the ranges of a run of length 3 (3 + 2 + 1). One column behaves the same way:[[1], [1], [1]]also gives 6. - All ones. A 2x2 matrix of ones gives 9, which is (2 · 3 / 2) times (2 · 3 / 2).
- All zeros. No column is ever intact, and the answer is 0.
- Forgetting to reset
full_col. A zero found for one top row would carry into the next, and valid rectangles would be missed. - Not resetting
curr_lengthon a zero column. The run would continue across a gap and count ranges that include a column with a 0. - Adding only when a column is intact. That works too, but adding at every column keeps the code shorter, since
curr_lengthis 0 after a break.
Testing
[[1, 0, 1], [1, 1, 0], [1, 1, 0]]gives 13.[[0, 1, 1, 0], [0, 1, 1, 1], [1, 1, 1, 0]]gives 24.[[1, 1, 1]]gives 6.[[1, 1], [1, 1]]gives 9.[[0]]gives 0.
