Search element in sorted matrix

Search element in sorted matrix

Given a sorted matrix, of N X M and element e, find the position (i,j) of e if it is present in the matrix. This problem is known as a search element in the 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.

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

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

The 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 the 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, the complexity of the algorithm to search in row and column sorted matrix is O(N+M), where N is the number of rows and M is the number of columns.

Search in sorted matrix implementation using binary search

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 an 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 the 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 the leftmost bottom element to the middle element of a matrix?  Thinking being, that is the only thing you can change, as matrix and element are already given to you and you cannot modify them. If you read optimizations on quicksort, this kind of thinking comes naturally, to vary the initial assumption of the solution to see if we can do better?

Search element in sorted matrix optimization

What if we take the middle element of the matrix, M[i][j] as a 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 the left top quadrant are less than M[i][j] for sure.
All elements in the right top may be less than or greater than the middle element. We cannot deduce anything for this quadrant and we need to dig deeper.

All elements in the right bottom are greater than the middle element.
All elements in the left bottom quadrant are either less or greater than middle element and hence as the 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 the relationship between e and middle element M[i][j], we can eliminate one of two quadrants, hence reducing the problem to 3/4th of the 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

Implementation note: Observe that we always end up searching in top right matrix no matter if the element is greater or less than the middle.
If we take that matrix separately and check always, rest part to be searched is either horizontal bottom matrix or vertical left matrix. The 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 > rowEnd || columnStart > 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 topmost right 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 the vertical matrix
              or lower horizontal matrix */

              if(element > 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;
    }
}

The complexity of above code is less than O(N^1.58). Every time we will have 3 N/2 size submatrices.

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

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