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 ???
Asked
Active
Viewed 912 times
9
-
Interesting question. Are you looking for just one region? How large are N and k typically, and what is the probability distribution of 1's and 0's? How fast does the algorithm need to be? I guess you don't know the answers, because this is an interview question, but that's what I would ask. – Thomas Mueller Sep 18 '10 at 13:18
-
It's pretty essential to know a bit more. If p is the probability of a 1, and k / p is much smaller than N, then the *easiest* way is to just try a single row or column. Take a 1xk region, count the number of ones, then add cells to the end until you have k ones. If k /p is much smaller than N, this has a high probability of working. Of course, if one row doesn't fit the requirements, you can move on to the next ... you have N of them after all. But what is 'best' anyway? Best worst case time? Best average case time? Smallest result rectangle area? – Joren Sep 18 '10 at 13:37
-
1A similar question is here: http://stackoverflow.com/questions/1726632/dynamic-programming-largest-square-block – bobobobo Sep 18 '10 at 13:41
-
For *any* rectangle that satisfies the requirements, you could start on the first row until you find a 1, then try the next row until you find another 1, then continue trying the remaining elements of the first row... while decrementing k and exhausting each row in turn. That way, you'll definitely get a rectangle :-) But there's no way I could say that's the *best* method - that depends on what is the measure of 'best'! I'm also obviously thinking of matrix-type operations (only familiar with Ruby & Python there). – Dave Everitt Sep 18 '10 at 14:20
-
@ravi: the link bobobobo gave only solves the problem for square blocks! – yassin Sep 18 '10 at 22:28
2 Answers
3
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).
Max
- 4,792
- 4
- 29
- 32
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.
IVlad
- 43,099
- 13
- 111
- 179
-
-
@Yassin Ezbakhe - I mean a consecutive sequence of rows. Consider a matrix that has 5 rows numbered 1 to 5. Rows 2, 3 and 4 form a sequence of rows. Treat those rows as a vector (the columns of those rows are elements of the vector) and apply the algorithm for the simpler problem on it. As there are `O(N^2)` such sequences of rows and the algorithm for the simpler problem is `O(N)` and must be applied on all sequences of rows, the total complexity of the solution is cubic. – IVlad Sep 18 '10 at 22:56
-
If you have the matrix [[0,1,1,1,1,0],[0,1,1,1,1,0],[0,1,1,1,1,0]], how would you extract the 3x4 all ones rectangle? – yassin Sep 18 '10 at 23:47
-
-
@IVlad: What if you have the matrix [[0, 1, 1, 1, 0], [1, 1, 1, 1, 1]]? For k = 8, your algorithm will give a solution, even if there is none. And, you also have to iterate k from N^2 to 0 to find the solution, which raises the worst-case cost to O(N^5). – yassin Sep 19 '10 at 10:12
-
@Yassin Ezbakhe - Why is there no solution? The entire matrix contains 8 zeroes, and my algorithm will find it. I don't have to iterate `k` either. If you're talking about the worst case of a hash table, then that's also very unlikely, if not impossible in this case. Can you provide an example where the worst case would occur? Even then, you can get `O(N^3 log N)` by using a set instead of a hashtable. – IVlad Sep 19 '10 at 10:19
-
@IVlad: Sorry, I was thinking in another problem (find the largest rectangle block of only ones). Your solution is 100% correct for what is asked for. +1 – yassin Sep 19 '10 at 10:24