• Tweet

• Tweet

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)