Rectangular region in an array

Question

Given an N*N matrix having 1's an 0's in them and given an integer k,what is the best method to find a rectangular region such that it has k 1's in it ???

Answer 1

I can do it with O(N^3*log(N)), but sure the best solution is faster. First you create another N*N matrix B (the initial matrix is A). The logic of B is the following:

B[i][j] - is the number of ones on rectangle in A with corners (0,0) and (i,j).

You can evaluate B for O(N^2) by dynamic programming: B[i][j] = B[i-1][j] + B[i][j-1] - B[i-1][j-1] + A[i][j].

Now it is very easy to solve this problem with O(N^4) by iterating over all right-bottom (i=1..N, j=1..N, O(N^2)), left-bottom (z=1..j, O(N)), and right-upper (t=1..i, O(N)) and you get the number of ones in this rectangular with the help of B:

sum_of_ones = B[i][j] - B[i][z-1] - B[t-1][j] + B[t-1][z-1].

If you got exactly k: k==sum_of_ones, then out the result.

To make it N^3*log(N), you should find right-upper by binary search (so not just iterate all possible cells).

Answer 2

Consider this simpler problem:

Given a vector of size N containing only the values 1 and 0, find a subsequence that contains exactly k values of 1 in it.

Let A be the given vector and S[i] = A[1] + A[2] + A[3] + ... + A[i], meaning how many 1s there are in the subsequence A[1..i].

For each i, we are interested in the existence of a j <= i such that S[i] - S[j-1] == k.

We can find this in O(n) with a hash table by using the following relation:

S[i] - S[j-1] == k => S[j-1] = S[i] - k

let H = an empty hash table
for i = 1 to N do
  if H.Contains (S[i] - k) then your sequence ends at i
  else
    H.Add(S[i])

Now we can use this to solve your given problem in O(N^3): for each sequence of rows in your given matrix (there are O(N^2) sequences of rows), consider that sequence to represent a vector and apply the previous algorithm on it. The computation of S is a bit more difficult in the matrix case, but it's not that hard to figure out. Let me know if you need more details.

Update: Here's how the algorithm would work on the following matrix, assuming k = 12:

0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0

Consider the first row alone:

0 1 1 1 1 0

Consider it to be the vector 0 1 1 1 1 0 and apply the algorithm for the simpler problem on it: we find that there's no subsequence adding up to 12, so we move on.

Consider the first two rows:

0 1 1 1 1 0
0 1 1 1 1 0

Consider them to be the vector 0+0 1+1 1+1 1+1 1+1 0+0 = 0 2 2 2 2 0 and apply the algorithm for the simpler problem on it: again, no subsequence that adds up to 12, so move on.

Consider the first three rows:

0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0

Consider them to be the vector 0 3 3 3 3 0 and apply the algorithm for the simpler problem on it: we find the sequence starting at position 2 and ending at position 5 to be the solution. From this we can get the entire rectangle with simple bookkeeping.