Fast, with explanations - Partial sums, c++, 24ms (better than 100%)


  • 0
    G

    This is my solution, which relies on Dynamic Programming principles.
    It uses O(n) space and runs in O(n) time, where 'n' is the size of the input (the size of the matrix).
    Look at the following image and read the comments in the code:

    sub matrices coloured areas

    class NumMatrix {
        // partialSums is of the same size as matrix
        // each cell, [row][col] has the sum of all the elements in the sub matrix (0,0),(row,col)
        vector<vector<int>> partialSums;
    public:
        NumMatrix(vector<vector<int>> &matrix) : partialSums(matrix.size()) {
            if (matrix.empty() || matrix[0].empty()) return;
            
            // construct partialSums in a dynamic programming way
            for (int row = 0; row<matrix.size(); row++) {
                partialSums[row].resize(matrix[row].size());
                for (int col = 0; col<matrix[row].size(); col++) {
                    // current cell
                    int sum = matrix[row][col];
                    // sum of sub matrix (0,0)-(row-1,col)
                    if (row > 0) sum += partialSums[row - 1][col];
                    // sum of sub matrix (0,0)-(row,col-1)
                    if (col > 0) sum += partialSums[row][col - 1];
                    // we actual counted the sub matrix (0,0)-(row-1,col-1) twice
                    if (row>0 && col>0) sum -= partialSums[row - 1][col - 1];
                    partialSums[row][col] = sum;
                }
            }
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) {
            // sum of sub matrix (0,0)-(row2,col2) - 
            //     all the colored areas, including the target sub matrix
            int sum = partialSums[row2][col2];
            // deduct the sum of sub matrix (0,0)-(row2,col1-1)
            //     the green and purple areas
            if (col1>0) sum -= partialSums[row2][col1 - 1];
            // deduct the sum of sub matrix (0,0)-(row1-1,col2)
            //     the blue and purple areas
            if (row1>0) sum -= partialSums[row1 - 1][col2];
            // since we deducted the purple area twice, you should re-add the purple area
            if (col1>0 && row1>0) sum += partialSums[row1 - 1][col1 - 1];
            return sum;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.