← Back to DSA Animator
Search a 2D Matrix II LC #240 Medium Top-Right Staircase
Problem

Write an efficient algorithm that searches for a value target in an m × n integer matrix where each row is sorted left-to-right and each column is sorted top-to-bottom.

Example 1
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
Explanation: 5 is at position (1,1).
Example 2
Input: same matrix, target = 20
Output: false
Explanation: 20 is not present in the matrix.
Constraints: 1 ≤ m, n ≤ 300  |  −10⁹ ≤ matrix[i][j] ≤ 10⁹  |  All rows and columns sorted ascending.
Try Examples
Custom:
Approach
Start at top-right corner: larger than target → go left; smaller → go down
Each step eliminates an entire row or column. O(m+n) time.
Matrix Search
Current cell
Search trail
Eliminated
Found
Variables
r (row)
—
c (col)
—
val
—
target
—
decision
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Start at top-right corner: r=0, c=cols-1
2
Loop while r < rows and c ≥ 0
3
If m[r][c] == target → return true (found!)
4
If m[r][c] > target → move left (c--), eliminating column
5
If m[r][c] < target → move down (r++), eliminating row
6
Loop exits without finding → return false
Time
O(m+n)
Space
O(1)
Why Top-Right Works

The top-right corner is a unique decision point: values increase downward (via column sort) and decrease leftward (via row sort). So from any position we can always eliminate an entire row or column in a single comparison — just like a 2D binary search. Starting anywhere else would give us two "larger" directions or two "smaller" directions, making the choice ambiguous.