# Element in sorted 2d matrix

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
• 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 ?

• 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:

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.

## 2 thoughts on “Element in sorted 2d matrix”

1. aapke_papa says:

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

1. tarry says:

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