## fizzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Given a matrix in which each row and each column is sorted, write a method to find an element in it.

Sharing is caring!

Problem statement
Given a matrix in which each row and each column is sorted, write a method to find an element in it.

Solution
Assumptions:
1. Rows are sorted left to right in ascending order. Columns are sorted top to bottom in ascending order.
2. Matrix is of size $n \times m$.

This algorithm works by elimination. Every move to the left (–col) eliminates all the elements below the current cell in that column. Likewise, every move down eliminates all the elements to the left of the cell in that row.

Code

public class SearchMatrix {
public static boolean search(int arr[][], int x) {
int n = arr.length;
int m = arr.length;

int c = m - 1;
int r = 0;

while (r < n && c >= 0) {
if (x == arr[r][c]) {
return true;
} else {
if (x < arr[r][c]) {
c--;
} else {
r++;
}
}
}

return false;
}

public static void main(String[] args) {
int[][] arr = { { 1, 2, 3, 4, 5 }, { 11, 12, 13, 14, 15 }, { 21, 22, 23, 24, 25 }, { 31, 32, 33, 34, 35 },
{ 41, 42, 43, 44, 45 } };
System.out.println(search(arr, 35));
}
}