C++ easy solution, O(mn) to construct, O(1) to query


  • 0
    C

    I process the matrix into a sumMatrix of the same size, in which sumMatrix[i][j] stands for the region sum from matrix[0][0] to matrix[i][j]. Say if we wanna query the region sum from matrix[m][n] to matrix[s][t], it goes with

    sumMatrix[s][t] - sumMatrix[m - 1][t] - sumMatrix[s][n - 1] + sumMatrix[m - 1][n - 1]
    

    Special cases may arise when m equals 0 or n equals 0, which can be handled by construct a one size more sumMatrix, i.e.

    sumMatrix.size()  = matrix.size() + 1, sumMatrix[i].size() = matrix[i].size() + 1
    

    Or we may handle it within the query as I did.

    class NumMatrix 
    {
    private:
    	vector<vector<int>> sumMatrix;
    public:
        NumMatrix(vector<vector<int>> &matrix): sumMatrix(matrix) 
        {
        	if(matrix.empty()) return;
            for(int i = 0; i < matrix.size(); ++i)
            	for(int j = 1; j < matrix[0].size(); ++j)
            		sumMatrix[i][j] += sumMatrix[i][j - 1];
            for(int j = 0; j < matrix[0].size(); ++j)
            	for(int i = 1; i < matrix.size(); ++i)
            		sumMatrix[i][j] += sumMatrix[i - 1][j];
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) 
        {
        	if(row1 < 0 || col1 < 0 || row1 >= sumMatrix.size() || col1 >= sumMatrix[0].size())
                return 0;
            if(row1 == 0 && col1 == 0)
            	return sumMatrix[row2][col2];
            else if(row1 == 0)
            	return sumMatrix[row2][col2] - sumMatrix[row2][col1 - 1];
            else if(col1 == 0)
            	return sumMatrix[row2][col2] - sumMatrix[row1 - 1][col2];
            return sumMatrix[row2][col2] - sumMatrix[row1 - 1][col2] - sumMatrix[row2][col1 - 1] + sumMatrix[row1 - 1][col1 - 1];
        }
    };
    
    // Your NumMatrix object will be instantiated and called as such:
    // NumMatrix numMatrix(matrix);
    // numMatrix.sumRegion(0, 1, 2, 3);
    // numMatrix.sumRegion(1, 2, 3, 4);

Log in to reply
 

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