74. Search a 2D Matrix¶

Edited by Charles

Medium · Python · Array

Problem

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

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

Each row is sorted in ascending order. The first integer of each row is greater than the last integer of the previous row.

Original study notes follow, including intermediate snippets and earlier attempts.

Problem¶

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

Each row is sorted in ascending order.
The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return True if target exists in the matrix. Otherwise, return False.

Example¶

matrix =
[
    [1,  3,  5,  7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
]

target = 16

Output:

True

Because:

Each row is sorted
+
The first element of the next row
is greater than the last element of the previous row

the entire matrix can be considered as one sorted 1D array.

For example:

[
    [1,  3,  5,  7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
]

can logically be viewed as:

[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]

Therefore, we can directly apply Binary Search.

Importantly, we do not need to actually flatten the matrix.

Search Range¶

Suppose:

m = len(matrix)
n = len(matrix[0])

There are:

m × n

elements in total.

Therefore, if we treat the matrix as a 1D array, its indices are:

0, 1, 2, ..., m × n - 1

So:

left = 0
right = m * n - 1

Convert a 1D Index to a 2D Position¶

This is the most important part of the problem.

Suppose each row contains n elements.

For a 1D index mid:

row = mid // n
col = mid % n

Therefore:

matrix[mid // n][mid % n]

gives the element corresponding to index mid in the imaginary 1D array.

Example¶

Suppose:

matrix =
[
    [1,  3,  5,  7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
]

Here:

n = 4

If:

mid = 6

then:

row = 6 // 4 = 1
col = 6 % 4  = 2

Therefore:

matrix[1][2]

is:

This is exactly index 6 in the flattened array:

index:   0  1  2  3   4   5   6   7   8   9   10  11
         ↓  ↓  ↓  ↓   ↓   ↓   ↓   ↓   ↓   ↓   ↓   ↓

        [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
                              ↑
                            mid = 6

So the general mapping is:

1D index
    ↓
   mid
    ↓
row = mid // n
col = mid % n
    ↓
matrix[row][col]

Binary Search¶

Once we know how to access the element at mid, the rest is exactly the same as standard Binary Search.

Calculate:

mid = (left + right) // 2

Then get the corresponding matrix value:

row = mid // n
col = mid % n

value = matrix[row][col]

There are three cases.

Case 1: Found the Target¶

if value == target:
    return True

Case 2: Current Value Is Too Small¶

If:

value < target

then the target can only be on the right side.

Therefore:

left = mid + 1

Case 3: Current Value Is Too Large¶

If:

value > target

then the target can only be on the left side.

Therefore:

right = mid - 1

Overall Process¶

2D sorted matrix
       ↓
Treat it as a 1D sorted array
       ↓
left = 0
right = m × n - 1
       ↓
while left <= right
       ↓
mid = (left + right) // 2
       ↓
Convert mid to 2D coordinates
       ↓
row = mid // n
col = mid % n
       ↓
value = matrix[row][col]
       ↓
 ┌─────────────┬─────────────┐
 ↓             ↓             ↓
value          value          value
== target      < target       > target
 ↓             ↓              ↓
True       left=mid+1    right=mid-1

Why Does This Work?¶

The matrix satisfies:

matrix[i][0] > matrix[i - 1][n - 1]

Therefore, after logically connecting all rows together, the resulting sequence is still sorted.

For example:

Row 1:  1   3   5   7
                         ↓
Row 2: 10  11  16  20
                         ↓
Row 3: 23  30  34  60

is equivalent to:

1 < 3 < 5 < 7 < 10 < 11 < 16 < 20 < 23 < 30 < 34 < 60

Therefore, standard Binary Search can be applied to the entire matrix.

Key Formula¶

For a matrix with n columns:

row = index // n
col = index % n

This is a very useful mapping to remember:

1D index → 2D coordinates

index // number_of_columns → row
index %  number_of_columns → column

Complexity¶

There are:

m × n

elements.

Binary Search takes:

O(log(m × n))

time.

We do not create a flattened array, so the extra space complexity is:

O(1)

Key Takeaway¶

LeetCode 74 is essentially a standard Binary Search problem.

The only special part is converting a virtual 1D index into a 2D matrix position:

matrix[mid // n][mid % n]

So you can remember this problem as:

LC 74
=
Binary Search
+
1D → 2D index mapping

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	September 9, 2026

Python solution¶

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])

        left, right = 0, m * n - 1

        while left <= right:
            mid = (left + right) // 2

            row = mid // n
            col = mid % n

            if matrix[row][col] == target:
                return True

            elif matrix[row][col] < target:
                left = mid + 1

            else:
                right = mid - 1

        return False

Back to Bonus Array · All Algorithm notes