How to search in a row-wise and column-wise sorted matrix
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
mrows andncolumns 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:
- Start the search at the topmost and rightmost corner in the matrix, i.e.,
i=0, j=n-1. - 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.
- 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.
- 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++;
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 -1return new int[]{-1, -1};}int numRows = matrix.length;int numCols = matrix[0].length;int i = 0; // Loop invariable for the rowint j = numCols - 1; // Loop invariable for the columnwhile (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.