My sometimes naive solution with two hash


  • 0

    performance: estimated O((mn/c)^2), where c is const determined by local factor

    First, I flatten the 2D array into f(row, col) = row*column length + col.
    Then use two hash map to hold the already computed 2D sum.

    H <f(row1, col1), H<f(row2, col2) -> sum>>

    public class NumMatrix {
        private int[][] pre;
    	private HashMap<Integer, HashMap<Integer,Integer>> visited = new HashMap<>();
    	private int len;
    	public NumMatrix(int[][] matrix) {
    		if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
    			return;
    			//throw new IllegalArgumentException("Input matrix Err");
    		this.len = matrix[0].length;
    		this.pre = new int[matrix.length][matrix[0].length+1];
    		for (int i = 0; i < matrix.length; i++) {
    			for (int j = 1; j <= matrix[i].length; j++) {
    				pre[i][j] = pre[i][j-1] + matrix[i][j-1];
    			}
    		}
    	}
    
    	public int sumRegion(int row1, int col1, int row2, int col2) {
    		int offset1 = row1*this.len + col1;
    		int offset2 = row2*this.len + col2;
    		if (this.visited.containsKey(offset1)
    				&& this.visited.get(offset1).containsKey(offset2))
    			return this.visited.get(offset1).get(offset2);
    
    		visited.put(offset1, new HashMap<>());
    		int sum = 0;
    		for (int i = row1; i <= row2; i++) {
    			sum += this.pre[i][col2+1] - this.pre[i][col1];
    		}
    		visited.get(offset1).put(offset2, sum);
    		
    		return sum;
    	}
    }
    

Log in to reply
 

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