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.
471 Views |
(7 votes, avg: 3.86)
Loading ...
Answer »
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"); }Leave an Answer/Comment