aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-05 13:28:03 +0100
committerJack Sangdahl <[email protected]>2025-01-05 13:28:03 +0100
commitb218fc8b0fcd51654a4b9c92fdf57169f00d6ab3 (patch)
tree5004e480adbe7ff15b996002426f21deddec73bb
parent441ce5ccc60300de3e0380771f403bd37b2fc611 (diff)
downloadleetcode-b218fc8b0fcd51654a4b9c92fdf57169f00d6ab3.tar.gz
leetcode-b218fc8b0fcd51654a4b9c92fdf57169f00d6ab3.zip
304. range sum query 2d - immutable
-rw-r--r--range_sum_query_2d.c57
-rw-r--r--range_sum_query_2d.cpp21
-rw-r--r--range_sum_query_2d.py62
3 files changed, 139 insertions, 1 deletions
diff --git a/range_sum_query_2d.c b/range_sum_query_2d.c
new file mode 100644
index 0000000..833f104
--- /dev/null
+++ b/range_sum_query_2d.c
@@ -0,0 +1,57 @@
+// 304. Range Sum Query 2D - Immutable
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+typedef struct {
+ int **matrix;
+ int matrixSize;
+} NumMatrix;
+
+NumMatrix *numMatrixCreate(int **matrix, int matrixSize, int *matrixColSize) {
+ NumMatrix *obj = (NumMatrix *)malloc(matrixSize * sizeof(NumMatrix));
+ obj->matrix = (int **)malloc((matrixSize + 1) * sizeof(NumMatrix));
+ obj->matrixSize = matrixSize + 1;
+ for (int i = 0; i <= matrixSize; i++)
+ obj->matrix[i] = (int *)calloc(*matrixColSize + 1, sizeof(int));
+ for (int i = 1; i <= matrixSize; i++)
+ for (int j = 1; j <= *matrixColSize; j++)
+ obj->matrix[i][j] = (obj->matrix[i - 1][j] + obj->matrix[i][j - 1] -
+ obj->matrix[i - 1][j - 1] + matrix[i - 1][j - 1]);
+ return obj;
+}
+
+int numMatrixSumRegion(NumMatrix *obj, int row1, int col1, int row2, int col2) {
+ return (obj->matrix[row2 + 1][col2 + 1] - obj->matrix[row2 + 1][col1] -
+ obj->matrix[row1][col2 + 1] + obj->matrix[row1][col1]);
+}
+
+void numMatrixFree(NumMatrix *obj) {
+ for (int i = 0; i < obj->matrixSize; i++)
+ free(obj->matrix[i]);
+ free(obj->matrix);
+ free(obj);
+}
+
+int main() {
+ int matrix_input[5][5] = {{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}};
+ struct two_d_arr matrix;
+ two_d_arr_init(&matrix, 5, 5, matrix_input);
+ NumMatrix *obj =
+ numMatrixCreate(matrix.arr, matrix.row_size, matrix.col_size);
+ printf("%d\n", numMatrixSumRegion(obj, 2, 1, 4, 3)); // expect: 8
+ printf("%d\n", numMatrixSumRegion(obj, 1, 1, 2, 2)); // expect: 11
+ printf("%d\n", numMatrixSumRegion(obj, 1, 2, 2, 4)); // expect: 12
+ numMatrixFree(obj);
+ two_d_arr_free(&matrix);
+}
diff --git a/range_sum_query_2d.cpp b/range_sum_query_2d.cpp
index d50ea14..835354f 100644
--- a/range_sum_query_2d.cpp
+++ b/range_sum_query_2d.cpp
@@ -1,5 +1,14 @@
+// 304. Range Sum Query 2D - Immutable
#include "leetcode.h"
+/*
+ * 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 {
public:
vector<vector<int>> sum;
@@ -18,4 +27,14 @@ public:
}
};
-int main() {}
+int main() {
+ vvd(int) matrix = {{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}};
+ NumMatrix *obj = new NumMatrix(matrix);
+ printf("%d\n", obj->sumRegion(2, 1, 4, 3)); // expect: 8
+ printf("%d\n", obj->sumRegion(1, 1, 2, 2)); // expect: 11
+ printf("%d\n", obj->sumRegion(1, 2, 2, 4)); // expect: 12
+}
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))