Working on machines without understanding them ? Then you should be here..
Geographical location should not become a barrier to Share our knowledge.
Puzzles and Interview question are intended to be discussed here.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 ?
Solution: 1
1. Start from left bottom most cell.
2. If query is larger move right .
3. If query is smaller move up.
4. If you can’t move right or up and haven’t found the query yet, it means that the query does not exist.
Applying binary search for Rows and column may furthur reduce the complexity,,,
0 comments:
Post a Comment