C++ solution: O(1) for sumRegion function


  • 1
    T

    My idea is in constructor we build a sum_matrix in which element (i, j) is the sum of sub-matrix (0, 0)-->(i, j). Then for sumRegion we could directly calculate the sum of sub-matrix (row1, col1)-->(row2, col2). Not sure this is the fastest solution, just for your reference:

    class NumMatrix {
    public:
    NumMatrix(vector<vector<int>> &matrix) {
        sum_matrix = matrix;
        if(matrix.empty()) return;
        for(int i = 0; i < matrix.size() - 1; ++i)
            sum_matrix[i + 1][0] += sum_matrix[i][0];
        for(int j = 0; j < matrix[0].size() - 1; ++j)
            sum_matrix[0][j + 1] += sum_matrix[0][j];
        for(int i = 1; i < matrix.size(); ++i)
        {
            for(int j = 1; j < matrix[0].size(); ++j)
            {
                sum_matrix[i][j] += sum_matrix[i - 1][j] + sum_matrix[i][j - 1] - sum_matrix[i - 1][j - 1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        if(sum_matrix.empty()) return 0;
        int all = sum_matrix[row2][col2];
        int left = (col1 == 0) ? 0 : sum_matrix[row2][col1 - 1];
        int top = (row1 == 0) ? 0 : sum_matrix[row1 - 1][col2];
        int mid = (row1 == 0 || col1 == 0) ? 0 : sum_matrix[row1 - 1][col1 - 1];
        return all - left - top + mid;
        
    }
    private:
    vector<vector<int>> sum_matrix;//(i, j): (0,0)(i,j) sum
    };

  • 0
    K

    I tried the following and got a "Time Limit Exceeded" message.

    any thought on the following written in java?

    code:
    public class NumMatrix {

    private static int[][] wMatrix;
    
    public NumMatrix(int[][] matrix) {
        wMatrix = matrix;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
                
        int sum = 0; 
                
        if (wMatrix.length > 0)
        {
            for(int r=row1;r<row2 || r==row2 ;r++)
            {
                int a[] = Arrays.copyOfRange(wMatrix[r], col1, col2);
                sum  += IntStream.of(a).sum();
            }
        }
    
        return sum;
    }
    

    }


  • 0
    T

    Should you compute wMatrix in the constructor?


Log in to reply
 

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