4

So, this is a common interview question. There's already a topic up, which I have read, but it's dead, and no answer was ever accepted. On top of that, my interests lie in a slightly more constrained form of the question, with a couple practical applications.

Given a two dimensional array such that:

  • Elements are unique.
  • Elements are sorted along the x-axis and the y-axis.
  • Neither sort predominates, so neither sort is a secondary sorting parameter.
  • As a result, the diagonal is also sorted.
  • All of the sorts can be thought of as moving in the same direction. That is to say that they are all ascending, or that they are all descending.
  • Technically, I think as long as you have a >/=/< comparator, any total ordering should work.
  • Elements are numeric types, with a single-cycle comparator.
  • Thus, memory operations are the dominating factor in a big-O analysis.

How do you find an element? Only worst case analysis matters.

Solutions I am aware of:
A variety of approaches that are:
O(nlog(n)), where you approach each row separately.
O(nlog(n)) with strong best and average performance.

One that is O(n+m):
Start in a non-extreme corner, which we will assume is the bottom right.
Let the target be J. Cur Pos is M.
If M is greater than J, move left.
If M is less than J, move up.
If you can do neither, you are done, and J is not present.
If M is equal to J, you are done.
Originally found elsewhere, most recently stolen from here.

And I believe I've seen one with a worst-case O(n+m) but a optimal case of nearly O(log(n)).

What I am curious about:

Right now, I have proved to my satisfaction that naive partitioning attack always devolves to nlog(n). Partitioning attacks in general appear to have a optimal worst-case of O(n+m), and most do not terminate early in cases of absence. I was also wondering, as a result, if an interpolation probe might not be better than a binary probe, and thus it occurred to me that one might think of this as a set intersection problem with a weak interaction between sets. My mind cast immediately towards Baeza-Yates intersection, but I haven't had time to draft an adaptation of that approach. However, given my suspicions that optimality of a O(N+M) worst case is provable, I thought I'd just go ahead and ask here, to see if anyone could bash together a counter-argument, or pull together a recurrence relation for interpolation search.

Community
  • 1
  • 1
Jake Kurzer
  • 1,532
  • 4
  • 16
  • 25
  • "Elements are sorted along the x-axis, and the y-axis" - is that, each row is sorted and each column is sorted? – Mitro Dec 20 '10 at 23:41
  • Technically, they're also sorted along the diagonal, so yes. – Jake Kurzer Dec 20 '10 at 23:43
  • In the description of the O(n+m) method, do you mean "if J is _greater_ than the max, the target is not present", and compare just K, T in the max? Also, I may be missing something, but isn't `[ 100 200 ; 50 199 ]` a counter example, if the target is on the left of 100? – lijie Dec 20 '10 at 23:56
  • Might be. I sometime mix up my left and my right... Ah, I am dense, I think. Give me a minute or three. – Jake Kurzer Dec 21 '10 at 00:14
  • 3
    http://stackoverflow.com/questions/3723353/interview-question-how-to-efficiently-search-in-an-ordered-matrix had an accepted answer and it looks awfully similar to your proposed solution for O(n+m). – Don Roby Dec 21 '10 at 00:15
  • You are correct! I am dense. Let me fix the O(n+m) solution. – Jake Kurzer Dec 21 '10 at 00:17
  • the starting corner for the solution pointed to by don is one of the non-extreme corners, rather than either extreme. – lijie Dec 21 '10 at 00:27
  • And this is what I get for taking wretched notes. And being illiterate. – Jake Kurzer Dec 21 '10 at 00:30
  • I've revised my instance, and added a outbound link. I'm still not perfectly sure that I'm right about the optimality of the worst-case. – Jake Kurzer Dec 21 '10 at 00:34
  • for general m,n, O(n+m) is definitely not optimal (consider m = 1). for n = m, O(n) is optimal (because the diagonal between the non-extreme corners can be unordered). – lijie Dec 21 '10 at 01:15
  • The optimal bound is O(m + lg n), where m <= n. – jonderry Dec 21 '10 at 06:02
  • Make it into an answer with a proof? – Jake Kurzer Dec 21 '10 at 17:42

2 Answers2

0

An optimal O(m+n) solution is to start at the top-left corner, that has minimal value. Move diagonally downwards to the right until you hit an element whose value >= value of the given element. If the element's value is equal to that of the given element, return found as true.

Otherwise, from here we can proceed in two ways.

Strategy 1:

  1. Move up in the column and search for the given element until we reach the end. If found, return found as true
  2. Move left in the row and search for the given element until we reach the end. If found, return found as true
  3. return found as false

Strategy 2: Let i denote the row index and j denote the column index of the diagonal element we have stopped at. (Here, we have i = j, BTW). Let k = 1.

  • Repeat the below steps until i-k >= 0
    1. Search if a[i-k][j] is equal to the given element. if yes, return found as true.
    2. Search if a[i][j-k] is equal to the given element. if yes, return found as true.
    3. Increment k

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Murali Mohan
  • 709
  • 9
  • 4
0

Here's a proof that it has to be at least Omega(min(n,m)). Let n >= m. Then consider the matrix which has all 0s at (i,j) where i+j < m, all 2s where i+j >= m, except for a single (i,j) with i+j = m which has a 1. This is a valid input matrix, and there are m possible placements for the 1. No query into the array (other than the actual location of the 1) can distinguish among those m possible placements. So you'll have to check all m locations in the worst case, and at least m/2 expected locations for any randomized algorithm.

One of your assumptions was that matrix elements have to be unique, and I didn't do that. It is easy to fix, however, because you just pick a big number X=n*m, replace all 0s with unique numbers less than X, all 2s with unique numbers greater than X, and 1 with X.

And because it is also Omega(lg n) (counting argument), it is Omega(m + lg n) where n>=m.

Keith Randall
  • 22,985
  • 2
  • 35
  • 54