Trusted answers to developer questions

abhilash

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.

**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

**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

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:

- 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++;
```

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 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.

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.

**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

CONTRIBUTOR

abhilash

RELATED COURSES

View all Courses

Keep Exploring

Related Courses