diff options
Diffstat (limited to 'range_sum_query_2d.py')
-rw-r--r-- | range_sum_query_2d.py | 62 |
1 files changed, 62 insertions, 0 deletions
diff --git a/range_sum_query_2d.py b/range_sum_query_2d.py new file mode 100644 index 0000000..caffaa8 --- /dev/null +++ b/range_sum_query_2d.py @@ -0,0 +1,62 @@ +# 304. Range Sum Query 2D - Immutable + +""" +given a 2d matrix 'matrix', handle multiple queries of the following type: +calculate the sum of the elements of 'matrix' inside the rectangle defined by +its upper left corner '(row1, col1)' and lower right corer '(row2, col2)'. +you must design an algorithm where 'sumRegion' works on 'O(1)' time +complexity. +""" + + +class NumMatrix(object): + def __init__(self, matrix): + """ + :type matrix: List[List[int]] + """ + m, n = len(matrix), len(matrix[0]) + self.sum = [[0] * (n + 1) for _ in range(m + 1)] + for r in range(1, m + 1): + for c in range(1, n + 1): + self.sum[r][c] = ( + self.sum[r - 1][c] + + self.sum[r][c - 1] + - self.sum[r - 1][c - 1] + + matrix[r - 1][c - 1] + ) + + def sumRegion(self, row1, col1, row2, col2): + """ + :type row1: int + :type col1: int + :type row2: int + :type col2: int + :rtype: int + """ + row1, col1, row2, col2 = ( + row1 + 1, + col1 + 1, + row2 + 1, + col2 + 1, + ) + return ( + self.sum[row2][col2] + - self.sum[row2][col1 - 1] + - self.sum[row1 - 1][col2] + + self.sum[row1 - 1][col1 - 1] + ) + + +if __name__ == "__main__": + obj = NumMatrix( + [ + [3, 0, 1, 4, 2], + [5, 6, 3, 2, 1], + [1, 2, 0, 1, 5], + [4, 1, 0, 1, 7], + [1, 0, 3, 0, 5], + ] + ) + print(obj.sumRegion(2, 1, 4, 3)) + print(obj.sumRegion(1, 1, 2, 2)) + print(obj.sumRegion(1, 2, 2, 4)) |