Optimize 2D Range Sum Query for LeetCode Problem #304 in C

[cw4real]

The current Python implementation of the NumMatrix class for LeetCode Problem #304 efficiently handles multiple range sum queries on a 2D matrix using a prefix sum matrix. This task is to convert the Python implementation to C and ensure it maintains efficient performance for initialization and query operations. Here is the optimized C implementation:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int** sumMat;
    int rows;
    int cols;
} NumMatrix;

NumMatrix* numMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) {
    int ROWS = matrixSize;
    int COLS = matrixColSize[0];
    NumMatrix* obj = (NumMatrix*)malloc(sizeof(NumMatrix));
    obj->rows = ROWS + 1;
    obj->cols = COLS + 1;

    obj->sumMat = (int**)malloc((ROWS + 1) * sizeof(int*));
    for (int r = 0; r <= ROWS; ++r) {
        obj->sumMat[r] = (int*)calloc(COLS + 1, sizeof(int));
    }

    for (int r = 0; r < ROWS; ++r) {
        int prefix = 0;
        for (int c = 0; c < COLS; ++c) {
            prefix += matrix[r][c];
            obj->sumMat[r + 1][c + 1] = prefix + obj->sumMat[r][c + 1];
        }
    }

    return obj;
}

int numMatrixSumRegion(NumMatrix* obj, int row1, int col1, int row2, int col2) {
    row1++;
    col1++;
    row2++;
    col2++;
    int bottomRight = obj->sumMat[row2][col2];
    int above = obj->sumMat[row1 - 1][col2];
    int left = obj->sumMat[row2][col1 - 1];
    int topLeft = obj->sumMat[row1 - 1][col1 - 1];

    return bottomRight - above - left + topLeft;
}

void numMatrixFree(NumMatrix* obj) {
    for (int r = 0; r < obj->rows; ++r) {
        free(obj->sumMat[r]);
    }
    free(obj->sumMat);
    free(obj);
}

Explanation:

1. Structure Definition:
   • NumMatrix struct contains the prefix sum matrix and its dimensions.
2. Initialization:
   • numMatrixCreate initializes the prefix sum matrix.
   • Each element in the prefix sum matrix is calculated based on the given matrix.
3. Range Sum Query:
   • numMatrixSumRegion calculates the sum of elements in the specified submatrix.
4. Memory Management:
   • numMatrixFree frees the allocated memory for the prefix sum matrix.

[DavidYeLuo]

That's a really nice way to construct the matrix. Thank you for sharing!