DSA AnimatorDSA animations
Search a 2D Matrix LC #74 Medium Binary Search · Matrix
Problem

You are given an m × n integer matrix where each row is sorted in non-decreasing order and the first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in the matrix, or false otherwise. Must run in O(log(m × n)) time.

Example 1
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Explanation: Target 3 is at row 0, col 1 (virtual index 1).
Example 2
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Explanation: Target 13 is not present anywhere in the matrix.
Example 3
Input: matrix = [[1,1]], target = 0
Output: false
Constraints: 1 ≤ m, n ≤ 100  |  −10⁴ ≤ matrix[i][j], target ≤ 10⁴
Try Examples
Custom:
Approach
Treat m×n matrix as sorted 1D array of length m×n. Binary search on virtual index.
mid → row = mid/n, col = mid%n. Eliminate half per step. O(log(m×n)) time.
Matrix + Flattened View
Flattened virtual array  (index mid → matrix[mid/n][mid%n])
Variables
lo
—
hi
—
mid
—
val
—
target
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Flatten mentally: lo=0, hi=m*n-1
2
Loop while lo ≤ hi; compute mid=(lo+hi)/2
3
Map mid → matrix[mid/n][mid%n], get val
4
If val==target → return true
5
If val < target → lo=mid+1 (eliminate left half)
6
Else → hi=mid-1 (eliminate right half)
7
lo > hi: search exhausted → return false
Time
O(log(m·n))
Space
O(1)
Why This Works

Because each row is sorted and every row starts after the previous row ends, flattening the matrix gives a fully sorted 1D array. A virtual index mid maps bijectively to cell (mid/n, mid%n). Standard binary search then finds the target in O(log(m·n)) steps — equivalent to binary-searching an array of length m×n.

How to solve Search a 2D Matrix

LeetCode 74 · Medium · Matrix · Pattern: Binary Search

Why the obvious approach is slow

Checking every cell is O(m) times n. But the rules mean the whole matrix is one sorted list, read row by row.

The key idea

Binary search over positions 0 to m times n −1. Turn a position into a cell with row equal to position divided by the number of columns, and column equal to position mod the number of columns.

Remember

A matrix sorted row after row is one long sorted array. Divide and mod by the column count to find the cell.

Run the animation above on your own input, or watch the 1:25 video explanation of Search a 2D Matrix with a dry run and Java code.

More Matrix problems