Questions : you have a [n * n] array which is sorted both row wise and column wise. How do you find an element in this array in O(n) time ?
Answer 1.-
Let X be the bottom left element of the matrix and we need to find the position of an element K.
Now if K = X, we can return the position of X.
Else if K < X, then we can possibly eliminate that row as all the elements in that row are greater than or equal to X.
Else if X < K, then we can eliminate that column as all the elements in that column are lesser than X.
Now in each step, we eliminate either a row or coll which finally leads to that element.
Answer 1.-
Let X be the bottom left element of the matrix and we need to find the position of an element K.
Now if K = X, we can return the position of X.
Else if K < X, then we can possibly eliminate that row as all the elements in that row are greater than or equal to X.
Else if X < K, then we can eliminate that column as all the elements in that column are lesser than X.
Now in each step, we eliminate either a row or coll which finally leads to that element.
No comments:
Post a Comment