Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

data structures
algorithms
communitycreator

How to search in a row-wise and column-wise sorted matrix

abhilash

Problem overview

Given an m x n matrix and a target value, determine the location of the target value in the matrix. If the target value is not found in the matrix, print [Target Value] not found in the matrix.

Every row and column is sorted in increasing order in the given matrix.

Example 1:

Input:

  • matrix[4][4] =
{ {35,45,55,65},
  {40,50,60,70},
  {52,54,62,73},
  {57,58,64,75} };
  • target = 73

Output:

73 found at row - 3 and column - 4

Example 2:

Input:

  • matrix[4][4] =
{ {35,45,55,65},
  {40,50,60,70},
  {52,54,62,73},
  {57,58,64,75} };
  • target = 90

Output:

90 not found in the matrix

Algorithm

What observations can be made from the problem statement?

  • A matrix of m rows and n columns is given.
  • A target value is given which may or may not be present in the matrix.
  • Every row and column is sorted in increasing order in the given matrix.

The last observation is the key observation that helps build the algorithm.

The steps of the algorithm are as follows:

  1. Start the search at the topmost and rightmost corner in the matrix, i.e., i=0, j=n-1.
  2. If the target value is equal to the value at the position we are at, then return the position of the current row and column.
  3. If the target value is less than the value at the position we are at, then we can ignore all the values in the current column and continue the search to the next column. As the matrix is sorted row-wise and column-wise in ascending order, all the other values in the current column are greater than the target value.
  4. If the target value is greater than the value at the position we are at, then we can ignore all the values in the current row and continue the search to the next row. As the matrix is sorted row-wise and column-wise in ascending order, all the other values in the row are lesser than the target value.

The pseudo-code of the algorithm is as follows:

i = 0;
j = numCol - 1;

while i>=0 and i < numRow and j >= 0 and j < num
    if (target == matrix[i][j]):
       return (i,j)
    else if (target < matrix[i][j]):
        j--;
    else i++;
1 of 8

Code

import java.util.Scanner;

public class Main {

    private static int[] search(int[][] matrix, int target) {
        if (matrix.length == 0) {  // If there are no elements in the matrix return -1
            return new int[]{-1, -1};
        }

        int numRows = matrix.length;
        int numCols = matrix[0].length;

        int i = 0; // Loop invariable for the row
        int j = numCols - 1; // Loop invariable for the column

        while (i >= 0 && i < numRows && j >= 0 && j < numCols) {
            if (target == matrix[i][j])  return new int[]{i, j};
            else if (target < matrix[i][j])  j--;
            else i++;
        }

        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {35,45,55,65},
                {40,50,60,70},
                {52,54,62,73},
                {57,58,64,75}
        };
        
        Scanner scanner = new Scanner(System.in);
        int target = scanner.nextInt();

        int[] result = search(matrix, target);

        if(result[0] != -1 && result[1] != -1) {
            System.out.println(target + " found at row - " + (result[0] + 1) + " and column - " + (result[1] + 1));
        } else {
            System.out.println(target + " not found in the matrix");
        }
    }
}

Enter the input below

Time and space complexity

  • Time Complexity: O(m+n)

The while loop runs a maximum of row length or the column length of the matrix.

  • Space Complexity: O(1)

The algorithm doesn’t use any extra space.

Other approaches

Approach 1

Loop through all the elements in the matrix using a nested loop. If a match is found, return the row and column index of the matrix.

The time complexity of this approach is O(m * n), as we are checking every element of the matrix.

Approach 2

  • Row-wise binary search

As every row is sorted, run binary search on every row. The time complexity of this approach is O(m * log(n)), as we are running binary search on every row with n elements in each row.

  • Column-wise binary search

As every column is sorted, run binary search on every column. The time complexity of this approach is O(n * log(m)), as we are running binary search on every column with m elements in each column.

RELATED TAGS

data structures
algorithms
communitycreator
RELATED COURSES

View all Courses

Keep Exploring