diff options
author | Jack Sangdahl <[email protected]> | 2025-01-05 13:28:03 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-05 13:28:03 +0100 |
commit | b218fc8b0fcd51654a4b9c92fdf57169f00d6ab3 (patch) | |
tree | 5004e480adbe7ff15b996002426f21deddec73bb | |
parent | 441ce5ccc60300de3e0380771f403bd37b2fc611 (diff) | |
download | leetcode-b218fc8b0fcd51654a4b9c92fdf57169f00d6ab3.tar.gz leetcode-b218fc8b0fcd51654a4b9c92fdf57169f00d6ab3.zip |
304. range sum query 2d - immutable
-rw-r--r-- | range_sum_query_2d.c | 57 | ||||
-rw-r--r-- | range_sum_query_2d.cpp | 21 | ||||
-rw-r--r-- | range_sum_query_2d.py | 62 |
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)) |