## Question

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

**Constraints:**

`m == matrix.length`

`n == matrix[i].length`

`1 <= n, m <= 300`

`-109 <= matrix[i][j] <= 109`

- All the integers in each row are
**sorted**in ascending order. - All the integers in each column are
**sorted**in ascending order. `-109 <= target <= 109`

## Algorithm

Same walk through as a question 378.Kth Smallest Element in a Sorted Matrix but much easier.

You start from left bottom corner element, if it's larger than the target, you go up otherwise you go right.

## Code

class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; int n = matrix[0].length; int i = m - 1, j = 0; while (i >= 0 && j < n) { if (matrix[i][j] > target) { i--; } else if (matrix[i][j] < target) { j++; } else { return true; } } return false; } }