Interview Question

Senior Software Engineer Interview New York, NY

Given an nxn matrix of numbers in ascending order in both

  dimensions how would you go about finding if the number y is in the matrix.
Answer

Interview Answer

1 Answer

0

Since elements of each row are in ascending order, we can apply binary search on each row. Following is my initial draft:

1. Go through every row one by one.
2. Check first element and last element of that row.
3. If our value falls within the range then perform a binary search on that row.
     3a. If the value is found, return true.
4. Otherwise go to next row.

Only when all rows have been checked in this way can we be sure that the element doesn't exist in the matrix.

EXECUTION TIME: Best case O(n + log n), Worst case O(n*log n)

CAVEAT: Make sure to go through all rows before deciding that the element doesn't exist. To know why, consider following matrix:

1 2 3 4
5 6 7 9
8 9 10 11
12 13 14 15

Say we are searching for 8. The range of second row is from 5 to 9 but a binary search won't show 8. But we can't return false here because 8 is in the next row.

SOME IMPROVEMENTS:

1. If value being searched (in the example above) is below 1 (element (0,0)) or above 15 (element (n,n)) then return false.

2. If first element of a row is greater than the element being searched then return false.

Okash on Oct 27, 2013

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up