# Leetcode 0240 Search 2d Matrix Ii

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

• Using Row Wise Column Wise Sorted Property
• For any element `a[i][j]` the following is true
• Elements towards left are always smaller
• `a[j] a[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]`
• 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`
``````
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size() - 1;
int n = matrix.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;
}

``````