0

We are given 2D matrix array (let's say length i and wide j) and integer k We have to find size of smallest rectangle, that contains this or greater sum F.e k=7

4 1
1 1
1 1
4 4

Anwser is 2, because 4+4=8 >= 7, if there wasn't last line, anwser would be 4, 4+1+1+1 = 7 >= 7

My idea is to count prefix sums Pref[k,l]=Tab[k,l]+Pref[k-1,l]+Pref[k,l-1] And then compare every single rectangle

Is this possible to make it faster? My idea is T(n)=O(n^2) (Where n is number of elements in matrix) I would like to do this in time n or n * log n

I would be really glad if someone would give me any tip how to do this :)

TheGrossSloth
  • 61
  • 3
  • Your prefix sums don't seem to calculate anything meaningful. Also if this problem could be solved in O(n^2) time as you claim, then it would be possible to solve the 2D maximum subrectangle problem in O(n^2 log U) time by binary searching on the largest value, where U is the sum of every positive number that appears in the input -- and that would be very surprising, since TTBOMK the state of the art for solving that problem is just a fraction under the O(n^3) generalisation of Kadane's algorithm to 2D. – j_random_hacker Feb 23 '16 at 19:14
  • 1
    @j_random_hacker Note that his `n` is the number of elements in the matrix, and not the size of one dimension. – amit Feb 23 '16 at 19:27
  • Quite right @amit, my mistake. I think the part about the prefix sums not calculating anything useful still stands though. – j_random_hacker Feb 23 '16 at 19:30
  • Yes, n is number of elements, my bad – TheGrossSloth Feb 23 '16 at 19:30
  • @TheGrossSloth: That was *my* bad actually... ;) You can define parameters how you want, I'm just accustomed to seeing n being the height (and width). – j_random_hacker Feb 23 '16 at 19:31
  • Ohh...ok, if we don't do it, for every rectangle we have to count everything one more time, in my case , we can get anwser much faster F.e We have rectangle from (a,b) to (c,d) So Sum=Pref[c,d]-Pref[a,d]-Pref[c,b]+Pref[a,b] – TheGrossSloth Feb 23 '16 at 19:35
  • The calculation you describe in your most recent comment (which is sometimes called "forming the integral image") is definitely sensible and a timesaver... But it doesn't seem to bear any relationship to the calculation of Pref[] that you describe in the main post. – j_random_hacker Feb 24 '16 at 12:29
  • Finally, if all the elements of the array are positive, you should mention that! – j_random_hacker Feb 24 '16 at 14:49

1 Answers1

1

First, create an auxillary matrix: sums, where:

sums[i,j] = A[0,0] + A[0,1] + .... + A[0,j] + A[1,0] + ... + A[1,j] + ... + A[i,j]

I think this is what you meant when you said "prefix matrix".

This can be calculated in linear time with dynamic programming:

sums[0,j] = A[0,0] + ... + A[0,j]
sums[i,0] = A[0,0] + ... + A[i,0]
sums[i,j] = sums[i-1,j] + sums[i,j-1] - sums[i-1,j-1] + A[i,j]
                                            ^
                                     elements counted twice

Now, assuming all elements are non negative, this is non decreasing, matrix, where each column and each row are sorted.

So, iterating the matrix again, for each pair of indices i,j, find the value closest yet smaller than sum[i,j]-k.

This can be done in O(sqrt(n)).

Do it for each such (i,j) pair, and you get O(n*sqrt(n)) solution.

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • Thanks for answer, in this problem elements are positive, but columns and rows are not sorted and that makes it harder :/ – TheGrossSloth Feb 23 '16 at 19:46
  • 1
    @TheGrossSloth The rows and columns of `sums` - the auxillary matrix you created are sorted. This is because the elements in the original matrix are all positive. – amit Feb 23 '16 at 19:52