6

Today I was asked the following question in an interview:

Given an n by n array of integers that contains no duplicates and values that increase from left to right as well as top to bottom, provide an algorithm that checks whether a given value is in the array.

The answer I provided was similar to the answer in this thread:
Algorithm: efficient way to search an integer in a two dimensional integer array?

This solution is O(2n), which I believed to be the optimal solution.

However, the interviewer then informed me that it is possible to solve this problem in sub linear time. I have racked my brain with how to go about doing this, but I am coming up with nothing.

Is a sub linear solution possible, or is this the optimal solution?

Community
  • 1
  • 1
the_james_marq
  • 63
  • 5
  • 2
    Duplicate of this thorough discussion right? http://stackoverflow.com/questions/2457792/given-a-2d-array-sorted-in-increasing-order-from-left-to-right-and-top-to-bottom – justhalf Sep 20 '13 at 05:40
  • 1
    Just to be clear, your input size is n^2, making 2n sublinear in the input size. Your interviewer wasn't simply observing this fact, was he? – foxcub Sep 20 '13 at 05:51
  • @justhalf wow, the answer there, do we really think O(n+m) or O(N * log(M/N) is going to be the best – clwhisk Sep 20 '13 at 06:10
  • Your array are pactically sorted. Their topography is just a bit weird. Try adapting binary search to work with it. – le-doude Sep 20 '13 at 06:29
  • 1
    [Thorough analysis of the problem here](http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster). – Raymond Chen Sep 20 '13 at 07:02
  • Isn't the accepted answer wrong? – foxcub Sep 20 '13 at 21:01

1 Answers1

4

The thing to ask yourself is, what information does each comparison give you? It let's you eliminate the rectangle either "above to the left" or "below to the right".

Suppose you do a comparison at 'x' and it tells you what your are looking for is greater:

XXX...
XXX...
XXx...
......
......

'x' - checked space
'X' - check showed this is not a possible location for your data
'.' - still unknown

You have to use this information in a smart way to check the entire rectangle.

Suppose you do a binary search this way on the middle column...

You'll get a result like

XXX...
XXX...
XXX...
XXXXXX
...XXX
...XXX

Two rectangular spaces are left over of half width and possibly full height. What can you do with this information?

I recommend recurring on the 2 resulting subrectangles of '.'. BUT, now instead of choosing the middle column, you choose the middle row to do your binary search on.

So the resulting run time of an N by M rectangle looks like T(N, M) = log(N) + T(M/2, N)*2

Note the change in indexes because your recursion stack switches between checking columns and rows. The final run time (I didn't bother solving the recursion) should be something like T(M, N) = log(M) + log(N) (it's probably not exactly this but it will be similar).

DanielV
  • 643
  • 4
  • 14
  • Yes...binary search the diagonal, and recur on the two blocks to upper right and lower left. – clwhisk Sep 20 '13 at 06:30
  • it has also been discussed here: http://stackoverflow.com/questions/2457792/given-a-2d-array-sorted-in-increasing-order-from-left-to-right-and-top-to-bottom and it's not `O(log n)`, but `O(N * log(M/N))` – justhalf Sep 20 '13 at 07:41
  • I think this algorithm is actually more like M*log(N) + N*log(M), but I'm not totally sure still. I doubt it's possible to do better than this approach though, given the constraints. – DanielV Sep 20 '13 at 08:57
  • Suppose the matrix is such that for every block you end up picking the "center" element. Then your recurrence becomes T(n) = 2*T(n/2) + log(n). That's not sublinear. – foxcub Sep 20 '13 at 17:38
  • To be precise, the recurrence is linear, it solves to n + (log n)^2 = O(n). – foxcub Sep 20 '13 at 21:05
  • Ah thanks foxcub. It is sublinear with input size, but not sublinear in the way the interviewer misdefined it. – DanielV Sep 20 '13 at 21:43
  • I guess the real issue for your answer is that the recurrence you define does not solve to log(M) + log(N), as you hoped, independent of the original definitions. – foxcub Sep 20 '13 at 21:51