Search a 2D Matrix II

The key idea

Start at the top-right corner, where the value is the largest in its row and the smallest in its column. From there every comparison eliminates a whole row or column: if the cell is bigger than target, the whole column below is too big, so move left; if it is smaller, the whole row to the left is too small, so move down. One pointer pair walks a staircase across the grid in O(m + n).

Problem

You are given an m x n integer matrix with the following two properties:

- Each row is sorted in ascending order from left to right.
- Each column is sorted in ascending order from top to bottom.

Given the matrix and an integer target, return true if target is in the matrix or false otherwise.

You must design a solution better than scanning every cell.

Constraints

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10^9 <= matrix[i][j] <= 10^9
All the integers in each row are sorted in ascending order.
All the integers in each column are sorted in ascending order.
-10^9 <= target <= 10^9

Examples

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

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 = 20 Output: false

Complexity

Time: O(m + n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →