Search element in sorted matrix

Search element in sorted matrix

Problem statement :  Given a sorted matrix, of N X M and element e, find position (i,j) of e if it is present in matrix. This problem is know as search element in sorted matrix.  When we say sorted matrix, it means that all elements in any row and column are in sorted order. For example,

[1,2,3,4,5
6,7,8,9,10
11,12,13,14,15
16,17,18,19,20
21,22,23,24,25]

is a sorted matrix. Now, concrete ask is to find element 18 in this matrix.

Search element in sorted matrix

What information we have in this question? We already know that all rows and columns are individually sorted. And challenge is to find an element. Does it ring bell? Rule of thumb is that if you want to find a element in sorted data set, think of binary search.  In binary search, we tend to discard half of the input set and focus our search on remaining data set.  It’s very intuitive in one dimensional array, how to formulate discarding rule in two dimensional matrix?

First challenge is to find the pivot around which we will move. In this case let’s start from leftmost bottom cell, that is M[N-1][0].

Process is to check if searched element e is less than or greater than element at leftmost bottom cell i.e M[N-1][0].
Let’s say i= N-1, and j=0;
1. If  e < M[i][j], move up in same column. Why? As we know that all the element in this column on the right will be definitely greater than M[i][j] and hence, by extension, greater than e, hence we cannot have e in that column.
However, there is possibility of finding e in column above it. Hence, we discard the current row. Decrease i and repeat.
2. If   e > M[i][j] , then move right in same row. Why? Because, all element in the same column will be less than M[i][j] and hence by extension less than e. So we discard current column. Increase j and repeat.
3. If   e equal to M[i][j] , return i, j as answer.

How many comparisons will happen in worst case and when it will happen? If e is at position M[0][N-1], then there will be M+N comparisons before we hit e. Hence, complexity of algorithm to search in row and column sorted matrix is O(N+M), where N is number of rows and M is number of columns.

Implementation : Find element in row and column sorted matrix

package com.company;

/**
 * Created by sangar on 30.12.17.
 */
public class Search {

    public static Position searchElement(int [][] M, int currentRow, int currentColumn,
                                         int columns, int element){

        //Check if we have a matrix to search in
        if( currentRow < 0 || currentColumn > columns) return new Position(-1, -1);

        //Check if the middle element is the searched element
        if(M[currentRow][currentColumn] == element){
            return new Position(currentRow,currentColumn);
        }
        else{
            if(element > M[currentRow][currentColumn]){
                return searchElement(M, currentRow, currentColumn+1, columns, element);
            }
            else{
                return searchElement(M, currentRow -1, currentColumn, columns, element);
            }
        }
    }

    public static void main(String[] args) {
        int[][] mat = new int[][] { {10, 20, 30, 40},
                {15, 25, 35, 45},
                {27, 29, 37, 48},
                {32, 33, 39, 50}};

        int rowcount = 4,colCount=4,key=20;
        Position position = searchElement(mat, rowcount-1, 0, colCount, key);

        System.out.println("Row: " + position.getRow() + ", Column: " + position.getColumn());
    }
}

We can avoid recursion and implement the same function in iterative way as shown below

package com.company;

/**
 * Created by sangar on 30.12.17.
 */
public class Search {

    public static Position searchElementIterative(int [][]M, int rows, int columns, int element){
        int i = rows-1;
        int j = 0;
        while( i>=0 && j <columns){
            if(M[i][j]== element){
                return new Position(i,j);
            }
            else if(M[i][j] < element){
                j++;
            }
            else{
                i--;
            }
        }
        return new Position(-1, -1);
    }

    public static void main(String[] args) {
        int[][] mat = new int[][] { {10, 20, 30, 40},
                {15, 25, 35, 45},
                {27, 29, 37, 48},
                {32, 33, 39, 50}};

        int rowcount = 4,colCount=4,key=20;
        Position position = searchElementIterative(mat, rowcount, colCount, key);

        System.out.println("Row: " + position.getRow() + ", Column: " + position.getColumn());
    }
}

We reduced complexity of search from O(M x N) which quadratic to O(M+N), which is linear. Can we do something sub-linear?  Can we discard more than one column or row at a time?  How about changing our pivot element from leftmost bottom element to middle element of matrix?  Thinking being, that is the only thing you can change, as matrix and element is already given to you and you cannot modify them. If you read optimizations on quick sort, this kind of thinking comes naturally, to vary the initial assumption of solution to see if we can do better.

What if we take the middle element of matrix, M[i][j] as pivot to compare with element e, what can be said about four quadrants middle element divides it into?

find element in row and column sorted matrix
Division of row and column sorted matrix for discarding purpose

All elements in left top quadrant are less than M[i][j] for sure.
All elements in right top may be less than or greater than middle element. We cannot deduce anything for this quadrant and we need to dig deeper.

All elements in right bottom are greater than middle element.
All elements in left bottom quadrant are either less or greater than middle element and hence as rightmost top quadrant, nothing can be said about it.

Two quadrants which contain either all less than or all greater than middle element.  Based on relationship between e and middle element M[i][j], we can eliminate one of two quadrants, hence reducing problem to 3/4th of  original problem.

Case 1 :
If   M[i][j] < e , then we need to search in all quadrants which may contain elements greater than middle. Discard quadrant which contains all elements less than middle.

Search element in sorted matrix
Discard upper left part as all elements are less than middle

Case 2:
If   M[i][j] > e , then search in all quadrants which may contain elements less than M[i][j]. Discard quadrant which contains elements definitely greater than M[i][j].

Search element in row and column sorted matrix
discard all lower right part as middle is greater than e

Search element in sorted matrix

Implementation note : Observe that we always end up searching in top right matrix no matter if element is greater or less than middle.
If we take that matrix separately and check always, rest part to be searched is either horizontal bottom matrix or vertical left matrix. Code is implemented keeping this in mind.

package com.company;

import com.company.Position;
public class Main {

public static Position searchElement(int [][] M, int rowStart, int rowEnd,
     int columnStart, int columnEnd, int element){

    //Check if we have a matrix to search in
    if(rowStart &gt; rowEnd || columnStart &gt; columnEnd) return new Position(-1, -1);

    int i = rowStart + (rowEnd-rowStart) / 2;
    int j = columnStart + (columnEnd-columnStart) / 2;

    //Check if the middle element is the searched element
    if(M[i][j] == element){
      return new Position(i,j);
    }
    else{
        //Always search in top most righ matrix.
        Position position = searchElement(M,
             rowStart,
             i,
             j+1,
             columnEnd,
             element);

         // If we found element in upper right matrix, return the position.
         if(isFound(position)){ return position; }

         else{
             /*Based on condition, search either left vertical matrix
              or lower horizontal matrix */

              if(element &gt; M[i][j]){
                 //search lower horizontal matrix
                  return searchElement(M,
                     i+1,
                     rowEnd,
                     columnStart,
                     columnEnd,
                     element
                  );
             }
             else{
                 //Search in right vertical matrix
                 return searchElement(M,
                     rowStart,
                     rowEnd,
                     columnStart,
                     j-1,
                     element
                );
           }
      }
   }
}

private static boolean isFound(Position position){
    return (position.getRow() != -1 &&
            position.getColumn() != -1);
}

public static void main(String[] args) {
    int[][] mat = new int[][] { {10, 20, 30, 40},
        {15, 25, 35, 45},
        {27, 29, 37, 48},
        {32, 33, 39, 50}};

     int rowcount = 4,colCount=4,key=48;
     Position position = searchElement(mat,
                           0,
                           rowcount - 1,
                           0,
                           colCount - 1,
                           key
     );
     System.out.println("Row: " + position.getRow() + ", Column: " + position.getColumn());
  }
}

Position can be defined as follows

package com.company;

/**
* Created by sangar on 30.12.17.
*/
public class Position {

    private int i;
    private int j;

    public Position(int i, int j){
        this.i = i;
        this.j = j;
    }

    public int getRow(){
       return i;
    }
    public int getColumn(){
        return j;
    }
}

Complexity of above code is less than O(N^1.58). Every time we will have 3 N/2 size sub matrices.

Word of caution : Both solutions are recursive in nature, which has n extra overhead of space on stack. If the recursion runs deep, this can be a problem and it is advise to use iterative solution. Recursive solution as usually no go in production.

Please share if you find something missing or wrong, or you have other idea to improve website. We would love to hear from you.
If you believe that you can explain algorithms problems in easier way to students and want to contribute to platform, please reach out to us on communications@algorithmsandme.com and we will get back.