leet-code/range-sum-query-2d-immutable/sol.rs

41 lines
1.4 KiB
Rust
Raw Permalink Normal View History

2022-06-04 11:25:07 +00:00
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);
*/