**Search an element in row-wise and column wise sorted 2-d array (n*n matrix )in O(n) complexity ??**

Check: Element searched is present in matrix(Element should be lesser than top right and greater than bottom left of matrix)

- Let Element to find: x
- Start with top-right element.
- Compare this element with x :
- If > x , move left?
- If < x , move down
- Repeat till you find the element

Complexity : n+n=O(n)

For m*n matrix , complexity would be m+n= O(m){if m >>> n} or O(n)(If n >>> m)

**Find kth (k < n*n)Max element in such a row wise and column wise sorted matrix ?**

- Start with top-right element.
- Compare left element(l) with down element(d) :
- If l> d , move left?
- If d>l , move down
- if left most element of any other row reached , then move down only
- if bottom most element of any other column reached , then move down only
- Repeat till you find the element

Complexity : n+n=O(n)

For m*n matrix , complexity would be m+n= O(m){if m >>> n} or O(n)(If n >>> m)

# Resolving technical problems:

Solve your technical problems instantly

We provide Remote Technical Support from Monday to Sunday, 7:00PM to 1:00 AM

Mail your problem details at [email protected] along with your mobile numberand we will give you a call for further details. We usually attend your problems within 60 minutes and solve it in maximum 2 days.

it does not work i guess

10 20 30 40

15 25 35 45

24 29 37 48

32 33 39 50

8th largest is 33 but as per your logic 33 is 6th largest

No ,

The example taken is a bit modified from problem statement, It would work as follows here :

50 -> 48 -> 45 -> 40 -> 30 -> 35 -> 37 -> 39 -> 33

30 wouldn’t be considered since it’s a smaller element , so 33 would come out to be 8th largest