# Leetcode 0240 Search 2d Matrix Ii

## Meta Data

### Link

### Tags

### Similar

- Other solutions at Leetcode-0074-search-2D-matix

## Problem Statement

- Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.

### Example

```
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
```

## Solution Approaches

### O(N * M) Brute Force Linear Search

- Implement a simple Linear Search Algorithm for matrix

### O(N * Log(M)) Binary Search Row Wise

- As rows are sorted perform Binary Search Algorithm on each
- If
`target`

is not found at the end of search then move to the next row - Time for binary search is
`log M`

which is applied on`N rows`

so`O(N * Log(M))`

in total.

### O(N+M) Top Right Approach

- Link
- 21 Search in Row wise And Column wise Sorted Array - YouTube by [[ Aditya Verma ]]

- Using Row Wise Column Wise Sorted Property
- For any element
`a[i][j]`

the following is true- Elements towards left are always smaller
`a[0][j] a[1][j] ... a[i-1][j] < a[i][j]`

- Elements towards down are always bigger
`a[i][j+1] a[i][j+2] ... a[i][m] > a[i][j]`

- Elements towards left are always smaller
- This makes the property applicable for Binary Search Algorithm type implementation
- Starting from Top Left we can move in two directions
`down to get larger and left to get smaller`

- For any element

```
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size() - 1;
int n = matrix[0].size() - 1;
int i = 0;
int j = n;
while (i <= m and j >= 0) {
if (matrix[i][j] == target) {return true;}
else if (matrix[i][j] < target) {i++;}
else {j--;}
}
return false;
}
```

Return to DSA