Interview Questions And Answers 
-
Given an N x M two dimensional array of integers where all rows and columns are sorted in ascending order, write a function that can determine if a certain value exists in the array.
4,822 Views |
(20 votes, avg: 4.4)
Loading ...
Answers »
Our Sponsors
Our Sponsors
The optimal solution has a M+N cost. I’ll describe the algorithm, since the comment editor may swallow the code if I don’t edit it properly:
- You have to start from the [M-1][0] or the [0][N-1] corners. Because of the distribution of values in the matrix, when you start form one of those corners, the value you look for can be in only one direction (for [M-1][0], all values to the right on the row are larger, and all values up on the column are smaller.) If you started from [0][0] all values to the right on the row and below on the column are larger so the value may be anywhere. Same for [M][N], all values on the row and column are smaller.
- Indexes are i for row and j for column
- Start from [M-1][0] (i=M-1, j=0).
- If the search value is larger than array[i][j], move right on the row (j++)
- If the search value is smaller than array[i][j] move up on the column (i–)
- otherwise you found it, exit the loop
- the loop goes on as long as the value is not found and both i and j are larger than or equal to zero and smaller than their max limits (M and N, respectively). If i or j becomes invalid, the value is not in the array.
Small tweaks can be added to reduce the solution space even further - e.g. - if both the leftmost and the rightmost values on a row are larger than the value we search for, skip that row altogether and move to the one above it.
Code (chances are that the snippet may be cut off… fingers crossed). Give it a try… it works
int arr[6][5] = { {1, 3, 7, 9, 11}, {2, 6, 8, 12,19}, {7, 9, 13,17,20}, {9, 14,15,18,30}, {12,16,18,22,33}, {31,32,36,38,39}}; const int M = 6; const int N = 5; void search(int arr[][], int val) { int i = M-1; int j = 0; bool found = false; while(i>=0 && i<M && j>=0 && j<N && !found) { printf("%dn", arr[i][j]); if(arr[i][j]==val) { printf ("found at [%d][%d]", i, j); found = true; } else if(arr[i][j]<val) j++; else i--; } if (!found) printf ("not found"); }Why not O(logm + logn)?
Fritz Stugren ’s solution is a clever one but not all “optimal solution”. The obviours one is applied binary search to M row which give you O(M*logN) assuming M is much less than N. If M is close to N,
then you want search first row first, throw out some columns. Then you search the first column of remaining array, throw out some rows. And so on.
The optimal solution, I think, is O(logN* logN).
j being column, shouldnt the else if check provided by Frizt should be like:
else if(val
Leave an Answer/Comment