19 ms concise and easy understanding C++ solution, beating 90%

  • 0

    Below is my solution for this problem. My idea comes from 1D immutable sumRegion problem. Since matrix remains the same, we do not need to save a copy of matrix. Instead, we calculate a (nrow+1) by (ncol+1) matrix called _Region. All entries in the first column and row will be zero, which means you do not need to consider corner problems on the edges. Although it takes more than nrow+ncol-1 space, it offers us ease in making our code concise.

    class NumMatrix {
        vector<vector<int>> _Region;  // _Region(i+1, j+1)  means the sum from matrix(0, 0) to (i, j)
        NumMatrix (vector<vector<int>> &matrix) {
            if (!matrix.size() || !matrix[0].size()) {
            } // Not empty matrix
            int numRow = matrix.size();
            int numCol = matrix[0].size();
            _Region = vector<vector<int>> (numRow+1, vector<int> (numCol+1));
            for (int i = 0; i < numRow; ++i)
                for (int j = 0; j < numCol; ++j)
                    _Region[i+1][j+1] = _Region[i][j+1] + _Region[i+1][j] - _Region[i][j] + matrix[i][j]; //Calculate Region entry, you can draw a graph that makes it easy to understand. 
        int sumRegion(int row1, int col1, int row2, int col2) {
            return _Region[row2+1][col2+1]-_Region[row1][col2+1]+_Region[row1][col1]-_Region[row2+1][col1]; // Same technique in calculating Region entry. 

Log in to reply

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