How to find if a subarray has a specific sum inside a 2D array in Java ?

Question

I am trying to solve a Image matching problem by comparing the average color of pixels present in both the source and pattern image. I have reduced this problem to a sub array sum problem, but cannot figure out a way to solve it.

Lets say i have a 2D array ARR with all positive integers. I have a number x( which is the average of the pixel colors present in a small pattern image). I just need to find any subarray in ARR which has the exact sum x. I found a similar problem which could be solved with Dynamic programming here.

http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

But that talks about finding a subarray with maximum sum and not the sum which was already given.

So if this the given array.

3   4   8   9   3
2   10  4   2   1
8   1   4   8   0
3   5   2   12  3
8   1   1   2   2

And if the given sum is 19, then it should return this window

3   4   8   9   3
2   10  4   2   1
8   1   4   8   0
3   5   2   12  3
8   1   1   2   2

And if the given sum is 23, then it should return this window

3   4   8   9   3
2   10  4   2   1
8   1   4   8   0
3   5   2   12  3
8   1   1   2   2
    

How can i find this efficiently ? Can Dynamic Programming be used here ? Please help me out here.

Answer 1

Using the same principle, but for a simpler problem. First, I precompute the cumulative sum for each column of the array, i.e., A[i][j] += A[i-1][j].

Then, for each pair of start/end rows (i1, i2), I treat them as a single array B[j], that means B[j] = A[i2][j] - A[i1-1][j]. Then, we need to find the subarray with the exact sum. As the array is composed only by positive numbers, I can find it in O(n).

Overall, this algorithm is O(n^3).

For the values you supplied, I was able to find some additionals arrays:

For target = 19:

Found between (0,0) and (1,1)
Found between (0,3) and (2,4)
Found between (0,2) and (4,2)
Found between (1,1) and (2,2)
Found between (1,2) and (2,4)
Found between (2,0) and (4,0)
Found between (3,3) and (4,5)

The target = 23:

Found between (0,2) and (1,3)
Found between (0,3) and (2,4)
Found between (2,0) and (3,2)
Found between (2,3) and (3,4)
Found between (3,1) and (4,4)

The code I used:

public static void main(String[] args) {
    int[][] A = {
            {3, 4, 8, 9, 3},
            {2, 10, 4, 2, 1},
            {8, 1, 4, 8, 0},
            {3, 5, 2, 12, 3},
            {8, 1, 1, 2, 2},
    };

    int target = 19;

    for (int i = 1; i < A.length; i++)
        for (int j = 0; j < A[i].length; j++)
            A[i][j] += A[i - 1][j];


    for (int i1 = 0; i1 < A.length; i1++) {
        for (int i2 = i1 + 1; i2 < A.length; i2++) {
            int j1=0, j2=0, s=0;

            while(j2<A[i1].length) {
                while(s<target && j2<A[i1].length) {
                    s += A[i2][j2] - (i1 > 0 ? A[i1-1][j2] : 0);
                    j2++;
                    if (s==target)
                        System.out.println(String.format("Found between (%d,%d) and (%d,%d)", i1, j1, i2, j2-1));
                }
                while(s>=target) {
                    s -= A[i2][j1] - (i1 > 0 ? A[i1-1][j1] : 0);
                    j1++;
                    if (s==target)
                        System.out.println(String.format("Found between (%d,%d) and (%d,%d)", i1, j1, i2, j2));
                }
            }
        }
    }
}