package com.interview.dynamic;

/**
 * Date 03/11/2016
 * @author Tushar Roy
 *
 * Given a 2D array find the sum in given range.
 *
 * Time complexity construction O(n*m)
 * Time complexity of query O(1)
 * Space complexity is O(n*m)
 * 
 * Reference
 * https://leetcode.com/problems/range-sum-query-2d-immutable/
 */
public class Immutable2DSumRangeQuery {
    private int[][] T;
    public Immutable2DSumRangeQuery(int[][] matrix) {
        int row = 0;
        int col = 0;
        if (matrix.length != 0) {
            row = matrix.length;
            col = matrix[0].length;
        }
        T = new int[row + 1][col + 1];
        for (int i = 1; i < T.length; i++) {
            for (int j = 1; j < T[0].length; j++) {
                T[i][j] = T[i - 1][j] + T[i][j - 1] + matrix[i - 1][j - 1] - T[i - 1][j - 1];
            }
        }

        for (int i = 1; i < T.length; i++) {
            for (int j = 1; j < T[0].length; j++) {
                System.out.print(T[i][j] + " ");
            }
            System.out.println();
        }

    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        row1++;
        col1++;
        row2++;
        col2++;
        return T[row2][col2] - T[row1 - 1][col2] - T[row2][col1 - 1] + T[row1 - 1][col1 - 1];
    }

    public static void main(String args[]) {
        int[][] input = {{3, 0, 1, 4, 2},
                        {5, 6, 3, 2, 1},
                        {1, 2, 0, 1, 5},
                        {4, 1, 0, 1, 7},
                        {1, 0, 3, 0, 5}};
        Immutable2DSumRangeQuery isr = new Immutable2DSumRangeQuery(input);
        System.out.println(isr.sumRegion(1, 1, 2, 2));
    }
}

@@ -124,10 +124,31 @@
 ange
+ defining a rectangle
 .%0A
-
  *%0A 
@@ -395,16 +395,17 @@
 %5B%5D%5B%5D T;%0A
+%0A
     publ
@@ -863,220 +863,13 @@
   %7D%0A
-%0A        for (int i = 1; i %3C T.length; i++) %7B%0A            for (int j = 1; j %3C T%5B0%5D.length; j++) %7B%0A                System.out.print(T%5Bi%5D%5Bj%5D + %22 %22);%0A            %7D%0A            System.out.println();%0A        %7D%0A%0A 
    %7D%0A
+
 %0A   
@@ -1348,16 +1348,100 @@
  0, 5%7D%7D;
+%0A%0A        int%5B%5D%5B%5D input1 = %7B%7B2,0,-3,4%7D, %7B6, 3, 2, -1%7D, %7B5, 4, 7, 3%7D, %7B2, -6, 8, 1%7D%7D;
 %0A       
@@ -1506,16 +1506,17 @@
 ry(input
+1
 );%0A     

update immutable2D rectangular sum solution