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.

just to clarify: are you looking for ANY suitable array or EVERY possible array? And does the dimension or the size of the subarray matter? — GameDroids
– GameDroids, Commented Mar 18, 2013 at 0:21
Actually i need to find out every possible array which matches. And i just have one constraint, the subarray should be 2 dimensional. No single element or set of elements in a single row or a single column should be considered as a result. — Pradep
– Pradep, Commented Mar 18, 2013 at 0:33
What about the typical sizes of your problem? What are the typical dimensions of your matrix? Does the sum have an upper bound? This can be useful, since the fact that all numbers in the matrix are positive implies that that the product of the dimensions of the rectangles must always be smaller than the sum. If the sum is small, the dimensions cannot be too big. — naitoon
– naitoon, Commented Mar 18, 2013 at 3:23
As I am dealing with Images, the dimensions of the matrix is actually the dimension of the test image. Typically somewhere under 3000 X 3000. The sums dont have any upper bound. Its just the sum of the rgb values of each pixel over the window. — Pradep
– Pradep, Commented Mar 18, 2013 at 23:13

Juan Lopes · Accepted Answer · 2013-03-18 02:41:16Z

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));
                }
            }
        }
    }
}

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related