jd
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
I think combination of recursion and binary search can solve this problem easily with O(log rows * log cols ) complexity.
In above case we will start with middle as it is the median of medians in the matrix, so the bottom-right part will be greater than the middle number and top left will be smaller than the middle number. In this way we can eliminate searching 1/4 of the matrix. If we continue doing it recursively with logically changing the matrix sizes and searching them recursively.
In the end we will be left with one row at the bottom of the tree where we need to do the binary search to determine the element.
I will try to code it and see if this works. Please let me know if you there is any problem with this approach .
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
@Roxanna Ya that's true. I realized it while implementing it. Thanks for clarification anyway. So the efficient algorithm would be the one which gives O(nrows+ncols), to follow a path and move right or down according to the value? or is there any other better solution
- jd January 30, 2014