Revisit: a 2D array sorted along the X and Y axis

Question

So this is a general interview question. There is already a topic that I read, but it is dead, and no answer was accepted. In addition, my interests lie in a slightly more limited form of the question, with a few practical applications.

Given a two-dimensional array such that:

• Elements are unique.
• Items are sorted along the x axis and y axis.
• No species prevails, therefore neither sorting is a secondary sorting parameter.
• As a result, the diagonal is also sorted.
• All species can be considered as moving in one direction. That is, they are all ascending, or that they are all descending.
• Technically, I think as long as you have a> / = / <comparator, any complete ordering should work.
• Elements are numerical types with a single cylinder comparator.
• Thus, memory operations are the dominant factor in analyzing large output.

How do you find the item? Only the worst analysis matters.

Solutions I Know About:
Different approaches that are: O (nlog (n)), where you approach each line separately.
O (nlog (n)) with strong best and average performance.

That O (n + m):
Start at the non-extreme corner, which we will take to 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 cannot do this, you are done, but J is not.
If M is equal to J, everything is ready.
It was originally found elsewhere, most recently stolen from here .

And I believe that I saw one with the worst case O (n + m), but the optimal case is almost O (log (n)).

What interests me:

I am currently happy that the naive break attack always goes to nlog (n). Aggressive attacks as a whole seem to have the optimal worst case O (n + m), and most of them do not end in the early stages of absence. I also wondered, as a result, if the interpolation probe can be no better than a binary probe, and therefore it occurred to me that one might think of this as a given problem of intersection with weak interaction between sets. My mind immediately switched to the intersection of Baeza-Yates , but I did not have time to prepare an adaptation of this approach. However, given my suspicions that the worst case optimality of O (N + M) is provable, I thought that I would just go and ask here to see if anyone could bash the counter argument or hide the recurrence relation to search for interpolation.

Answer 1

Here is the proof that it must be at least Omega(min(n,m)) . Let n >= m . Then we consider a matrix that has all 0 at (i,j) , where i+j < m , all 2 , where i+j >= m , with the exception of one (i,j) with i+j = m , which has 1 . This is a valid input matrix, and there are m possible placements for 1 . No request to the array (other than the actual location 1 ) can distinguish those m possible placements. Thus, you will need to check all the m locations in the worst case and at least m/2 expected locations for any randomized algorithm.

One of your assumptions was that the elements of the matrix must be unique, and I did not. However, it is easy to establish because you simply select a large number X=n*m , replace all 0 with unique numbers less than X , all 2 with unique numbers greater than X and 1 with X

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

Answer 2

The optimal solution O (m + n) should start in the upper left corner, which has a minimum value. Move diagonally down to the right until you click on an element whose value> = the value of this element. If the value of an element is equal to the value for this element, return will be found as true.

Otherwise, we can act in two ways.

Strategy 1:

• Move to the column and find the given element until we reach the end. If found, return found as true
• Move left in the line and look for the given element until we reach the end. If found, return found as true
• return found as false

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

• Repeat the steps below until ik> = 0
  • Search if [ik] [j] is equal to this element. if yes, return found as true.
  • Search if [i] [jk] is equal to this element. if yes, return found as true.
  • Increment k

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