aboutsummaryrefslogtreecommitdiff
path: root/range_sum_query_2d.py
diff options
context:
space:
mode:
Diffstat (limited to 'range_sum_query_2d.py')
-rw-r--r--range_sum_query_2d.py62
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))