CODEWITHSUNDEEP
algorithmmatrixtimesum
TheGrossSloth
TheGrossSloth

Reputation: 61

Algorithm-Find sum in matrix

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 :)

Upvotes: 0

Views: 447

Answers (1)

amit
amit

Reputation: 178441

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.

Upvotes: 1

Related Questions