Java solution take 4ms


  • 1
    I
    public class NumMatrix {
    	int[][] dp;
    	public NumMatrix(int[][] matrix) {
    		if(matrix.length > 0) {
    			this.dp = new int[matrix.length][matrix[0].length];
    			for(int i = 0; i < matrix.length; i++) {
    				int s = 0;
    				for(int j = 0; j < matrix[0].length; j++) {
    					s += matrix[i][j];
    					dp[i][j] = i == 0 ? s : s + dp[i-1][j];
    				}
    			}
    		}
    	}
    
    	public int sumRegion(int row1, int col1, int row2, int col2) {
    		if(row1 == 0 && col1 == 0) return dp[row2][col2];
    		if(row1 == 0) return dp[row2][col2] - dp[row2][col1-1];
    		if(col1 == 0) return dp[row2][col2] - dp[row1-1][col2];
    
    		return dp[row2][col2] - dp[row1-1][col2] - dp[row2][col1-1] + dp[row1-1][col1-1];
    	}
    }

Log in to reply
 

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