An interview question from Google [duplicate]

Question

Possible Duplicate:
Given a 2d array sorted in increasing order from left to right and top to bottom, what is the best way to search for a target number?

The following was asked in a Google interview:

You are given a 2D array storing integers, sorted vertically and horizontally.

Write a method that takes as input an integer and outputs a bool saying whether or not the integer is in the array.

What is the best way to do this? And what is its time complexity?

Answer 1

Start at the Bottom-Left corner of the Matrix and follow the rules stated below to traverse the matrix:

The matrix traversal is based on these conditions:

1. If the input number is greater than current number: Move Right
2. If the input number is less than current number: Move Up.
3. If the input number is equal to current number: Return Success
4. If the input number is not equal to current number and no transition is possible: Return Fail

Time Complexity: (Thanks to Martinho Fernandes)

The time complexity is O(N+M). In the worst case, the element searched for is in the upper-left corner, meaning you'll go up N times, and left M times.

Example

Input matrix:

--------------
| 1 | 4 | 6  | 
--------------
| 2 | 5 | 9  |
--------------
| *3* | 8 | 10 |
--------------

Number to search: 4

Step 1: Start at the cell where you have 3 (Bottom-Left).

3 < 4: Move Right

---

| 1 | 4 | 6  | 
--------------
| 2 | 5 | 9  |
--------------
| 3 | *8* | 10 |
--------------

Step 2: 8 > 4: Move Up

---

| 1 | 4 | 6  | 
--------------
| 2 | *5* | 9  |
--------------
| 3 | 8 | 10 |
--------------

Step 3: 5 > 4: Move Up

---

| 1 | *4* | 6  | 
--------------
| 2 | 5 | 9  |
--------------
| 3 | 8 | 10 |
--------------

Step 4:

4=4: Return the index of the number

Answer 2

I would start by asking details about what it means to be "sorted vertically and horizontally"

If the matrix is sorted in a way that the last element of each row is less than the first element of the next row, you can run a binary search on the first column to find out in what row that number is, and then run another binary search on the row. This algorithm will take O(log C + log R) time, where C and R are, respectively the number of rows and columns. Using a property of the logarithm, one can write that as O(log(C*R)), which is the same as O(log N), if N is the number of elements in the array. This is almost the same as treating the array as 1D and running a binary search on it.

But the matrix could be sorted in a way that the last element of each row is not less than the first element of the next row:

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

In this case, you could run some sort of horizontal an vertical binary search simultaneously:

1. Test the middle number of the first column. If it's less than the target, consider the lines above it. If it's greater, consider those below;
2. Test the middle number of the first considered line. If it's less, consider the columns left of it. If it's greater, consider those to the right;
3. Lathe, rinse, repeat until you find one, or you're left with no more elements to consider;

This method is also logarithmic on the number of elements.