41 lines
1.4 KiB
Rust
41 lines
1.4 KiB
Rust
struct NumMatrix {
|
|
sums_matrix: Vec<Vec<i32>>
|
|
}
|
|
|
|
|
|
/**
|
|
* `&self` means the method takes an immutable reference.
|
|
* If you need a mutable reference, change it to `&mut self` instead.
|
|
*/
|
|
impl NumMatrix {
|
|
// Generate an accumulating sum matrix in-place
|
|
// O(1) extra memory
|
|
fn new(mut matrix: Vec<Vec<i32>>) -> Self {
|
|
for row in (0..matrix.len()) {
|
|
let mut acc = 0;
|
|
for col in (0..matrix[0].len()) {
|
|
acc += matrix[row][col];
|
|
matrix[row][col] = acc;
|
|
if row != 0 {
|
|
matrix[row][col] += matrix[row-1][col];
|
|
}
|
|
}
|
|
}
|
|
NumMatrix { sums_matrix: matrix }
|
|
}
|
|
|
|
// Use the accumulating sums to get the sum of the region
|
|
// Space: O(1), Time: O(1)
|
|
fn sum_region(&self, row1: i32, col1: i32, row2: i32, col2: i32) -> i32 {
|
|
let top_rec = if row1 == 0 { 0 } else { self.sums_matrix[row1 as usize - 1][col2 as usize] };
|
|
let left_rec = if col1 == 0 { 0 } else { self.sums_matrix[row2 as usize][col1 as usize - 1] };
|
|
let rec_overlap = if row1 == 0 || col1 == 0 { 0 } else { self.sums_matrix[row1 as usize - 1][col1 as usize - 1] };
|
|
self.sums_matrix[row2 as usize][col2 as usize] - top_rec - left_rec + rec_overlap
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Your NumMatrix object will be instantiated and called as such:
|
|
* let obj = NumMatrix::new(matrix);
|
|
* let ret_1: i32 = obj.sum_region(row1, col1, row2, col2);
|
|
*/ |