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

 

 

 

 

2 thoughts on “Element in sorted 2d matrix”

  1. 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. 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

Leave a Reply

Your email address will not be published. Required fields are marked *