Search a 2D Matrix II

Medium

Write an efficient algorithm that searches for a target value in an m x n integer matrix.

The matrix has the following properties:

Integers in each row are sorted in ascending order from left to right.
Integers in each column are sorted in ascending order from top to bottom.

Return true if the target exists in the matrix, otherwise return false.

Example 1

Input

m = 5
n = 5
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

Explanation

The target 5 exists in the matrix.

Example 2

Input

m = 5
n = 5
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

Explanation

The target 20 does not exist in the matrix.

Constraints

m == matrix.length

n == matrix[i].length

1 <= m

n <= 300

-10^9 <= matrix[i][j] <= 10^9

All rows are sorted in ascending order.

All columns are sorted in ascending order.

-10^9 <= target <= 10^9

Hints:

Hint 1

Start from the top-right corner of the matrix.

Hint 2

At position (row, col):

If matrix[row][col] == target, return true.
If matrix[row][col] > target, move left.
If matrix[row][col] < target, move down.

Author & Technical Reviewer

Technically reviewed by: ExamAdda Technical Review Team

Technical Reviewers, ExamAdda

Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.

Published

Aug 26, 2026

Last updated

Aug 27, 2026

Content Verification Methodology

Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.

Report a correction:editorial@examadda.org

Auto

Loading editor...

Input

Expected Output