matrixRegionSum

matrixRegionSum

public class SummableMatrix {

	  private HashMap<Coordinate, Integer> cache;
	  
	  public SummableMatrix(int[][] matrix) {
	    cache = preprocess(matrix);
	  }
	
	  public static HashMap<Coordinate, Integer> preprocess(int[][] matrix) {
	    HashMap<Coordinate, Integer> result = new HashMap<Coordinate, Integer>();
	    Coordinate origin = new Coordinate(0,0);  
	    Coordinate bottomright = new Coordinate(matrix[0].length-1, matrix.length-1); 
	    for (int j = origin.y; j <= bottomright.y; j++) {
	    	for (int i = origin.x; i <=	 bottomright.x; i++) {
	    		int north, west, northwest, sum;
	    		north = west = northwest = sum = 0;
	    		if (i-1 >= 0) west = result.get(new Coordinate(i-1,j));
	    		if (j-1 >= 0) north = result.get(new Coordinate(i, j-1));
	    		if (i-1 >= 0 && j-1 >= 0) northwest = result.get(new Coordinate(i-1,j-1));
	    		sum = west + north - northwest + matrix[j][i];
	    		result.put(new Coordinate(i,j), sum);
	    	}
	    }
	    return result;
	  }
	  
	  public int getSum(Coordinate A, Coordinate D) {
		  /* For an nxn matrix the user will pass in coordinates
		   * where the origin is (0,0) and bottomright is (3,3).
		   * We accommodate for that by subtracting 1 from both A and D
		   */
		  
		  A.moveNorthWest();
		  D.moveNorthWest();
		  
		  Coordinate B = new Coordinate(D.x, A.y);
		  Coordinate C = new Coordinate(A.x, D.y);
		  int sumA = (A.x < 0 || A.y < 0) ? 0 : cache.get(A);
		  int sumB = (A.y < 0) ? 0 : cache.get(B);
		  int sumC = (A.x < 0) ? 0 : cache.get(C);
		  int sumD = (D.x < 0 || D.y < 0) ? 0 : cache.get(D);
		  return sumD - sumC - sumB + sumA;
	  }  
}

public class Coordinate {
  protected int x;
  protected int y;
  public Coordinate(int x, int y) {
    this.x = x;
    this.y = y;
  }
  
  public void moveNorthWest() {
	  x -= 1;
	  y -= 1;
  }
  
  @Override
  public boolean equals(Object o) {
	  if (o instanceof Coordinate) {
		 Coordinate c = (Coordinate) o;
		 if (this.x == c.x && this.y == c.y){
			 return true;
		 }
	  }
	  return false;
  }
  
  @Override 
  public int hashCode(){
	  return x+y;
  }
}