CareerCup

/*
Solution
--
I assume, the question draws towards doing many queries and few or no changes
on the matrix. You can prepare an array that will contain the # of ones in
the square (0,0,x,y). So, you need O(n*m) space and O(n*m) runtime to prepare
and O(1) to query.

Best is you draw it on a paper and then it's just like adding and subtracting
the area of squares:
[A][T][T][-][-]
[L][Q][Q][-][-]
[L][Q][Q][-][-]
[-][-][-][-][-]

let's assume we want to know how many 1's in Q: {x:1,y:1,w:2,h:2}
So, we take the value from {0,0,3,3} stored in mPreCalculated[3][3]
and subtract A,T,T and A,L,L from it and finally add A again.

in Java:
*/
public class MatrixCountOneFast {
    private int[][] mSumMatrix;
    private int mM;
    private int mN;
    public MatrixCountOneFast(int[][] input) {
        mN = input.length;
        mM = mN > 0 ? input[mN-1].length : 0;
        mSumMatrix = input.clone();
        for(int j = 0; j < mN; j++) {
            int lineSum = 0;
            for(int i = 0; i  < mM; i++) {
                lineSum += (input[j][i] > 0 ? 1 : 0);
                mSumMatrix[j][i] = lineSum + ( j > 0 ? mSumMatrix[j-1][i] : 0);
            }
        }
    }

    public int queryNoOfOne(int x, int y, int height, int width) {
        int x2 = x + width - 1;
        int y2 = y + height - 1;
        assert(x >= 0 && y >= 0 && x2 < mM && y2 < mN);
        if(height <= 0 || width <= 0) return 0;

        int sum = mSumMatrix[y2][x2];
        if(y > 0) sum -= mSumMatrix[y - 1][x2];
        if(x > 0) sum -= mSumMatrix[y2][x - 1];
        if(x > 0 && y > 0) sum += mSumMatrix[y - 1][x - 1];
        return sum;
    }

    public static void main(String[] args) {
        MatrixCountOneFast m  = new MatrixCountOneFast(new int[][]
                {
                        {1,1,0,0,1,0,1},
                        {1,0,1,0,0,1,1},
                        {0,1,1,1,0,1,0},
                        {0,1,0,1,0,0,1}
                });
        System.out.println(m.queryNoOfOne(0,0,1,1) == 1);
        System.out.println(m.queryNoOfOne(0,0,2,2) == 3);
        System.out.println(m.queryNoOfOne(0,0,2,2) == 3);
        System.out.println(m.queryNoOfOne(1,1,1,6) == 3);
        System.out.println(m.queryNoOfOne(2,2,2,2) == 3);
    }
}

Note that there is optimization for the O(N^2) pre calculation using a 2D segment tree, where changes in the matrix consume O(lg(N)lg(N)) and the same is true for querying. Then there is the addition to do something with lacy calculation by marking parts of the tree dirty and only calculate it when needed... this problem is pretty much open ended

You can precompute the number of ones at every position in a way that:

NumOfOnes(i, j) = NumberOfOnes(0-i, 0-j).... in other words at any index you should be able to tell the number of ones until that index from 0,0.
This precomputation will take O(n^2) time & O(n^2) memory but we will have to do so only once. Once you have that then finding number of ones is in subset is simply O(1) irrespective the size of grid.

public class Solution {
  private final Integr[][] cachedSum;
  private final Integer[][] matrix;

  public Solution(Integer[][] matrix) {
    if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
      throw new IllegalArgumentException("Pass in valid matrix");
    }
    this.matrix = matrix;
    Map<Point, Integer> cache = new HashMap<>();
    this.cachedSum = this.getPreCalculatedSum(matrix, matrix.length - 1, matrix[0].length - 1, cache);
  }

  // This is the api that will be called everytime and returns in O(1)
  public int getSum(int row1, int col1, int row2, int col2) {
    if(row1 < 0 || col1 < 0 || row1 > row2 || col1 > col2 || row2 >= matrix.length || col2 >= matrix[0].length) {
      throw new IllegalArgumentException("Please pass in valid cordiates");
    }
    int topDiagonalSum = row1 - 1 >= 0 && col1 - 1 >= 0 ? this.cachedSum[row1 - 1][col1 - 1] : 0;
    int topSectionSum = row1 - 1 >= 0 ? this.cachedSum[row1 - 1][col2] : 0;
    int leftSectionSum = col1 - 1 >= 0 ? this.cachedSum[row2][col1 - 1];
    return this.cachedSum[row2][col2] - leftSectionSum - topSectionSum + topDiagonalSum;
  }

  private int fillPreCalculatedSum(Integer[][] matrix, Integer[][] result, int row, int col, Map<Point, Integer> cache) {
    Point p = new Point();
    p.row = row; p.col = col;
    if(cache.contains(p)) {
      return cache.get(p);
    }
    else if(row < 0 || col < 0) {
      return 0;
    }

    int leftSum = col - 1 >= 0 ? this.getPreCalculatedSum(matrix, result row, col - 1, cache) : 0;
    int topSum = row - 1 >= 0 ? this.getPreCalculatedSum(matrix, result, row - 1, col, cache) : 0;
    int diagonalTopSum = row -1 >= 0 && col - 1 >= 0 ? this.getPreCalculatedSum(matrix, result, row - 1, col - 1, cache) : 0;
    int sum = matrix[row][col] + leftSum + topSum - diagonalTopSum;
    result[row][col] = sum;
    cache.put(p, sum);
    return sum;
  }

  private static class Point {
    public int row;
    public int col;
  }
}