aboutsummaryrefslogtreecommitdiff
path: root/range_sum_query_2d.c
diff options
context:
space:
mode:
Diffstat (limited to 'range_sum_query_2d.c')
-rw-r--r--range_sum_query_2d.c57
1 files changed, 57 insertions, 0 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);
+}