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)

Post Views:
962

Post navigation

C++ C C# Health concepts Leetcode Programming Data Streucture
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