LeetCode 074 - Search a 2D Matrix

2026-07-03

medium　array　binary search　matrix

If you're not familiar with binary search, check out LeetCode 704 - Binary Search first.

You are given an m x n 2D integer array matrix and an integer target.

• Each row is sorted in non-decreasing order.
• The first integer of every row is greater than the last integer of the previous row.

Return true if target exists within matrix, or false otherwise.

Can you write a solution that runs in O(log(m * n)) time?

Example 1:

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10

Output: true

Example 2:

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15

Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10,000 <= matrix[i][j], target <= 10,000

Solution 1:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # Approach: Binary Search on Each Row
        # 1. Iterate through every row.
        # 2. Run a standard binary search on each row.
        # 3. Return True as soon as a match is found; return False if no row contains it.
        # Time Complexity: O(M log N) — binary search on each of the M rows.
        # Space Complexity: O(1).
        for nums in matrix:
            l_idx, r_idx = 0, len(nums) - 1
            while l_idx <= r_idx:
                middle = (l_idx + r_idx) // 2
                if nums[middle] == target:
                    return True
                elif nums[middle] > target:
                    r_idx = middle - 1
                else:
                    l_idx = middle + 1
        return False

Solution 2:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # Approach: Two-Pass Binary Search (row first, then column)
        # 1. Binary search across rows: compare target against the first and last element
        #    of each row's midpoint to locate which row could contain the target.
        # 2. Once the target row is found, run a second binary search within that row.
        # 3. If the outer binary search exhausts without finding a valid row, return False.
        # Time Complexity: O(log M + log N) = O(log(M * N)) — two independent binary searches.
        # Space Complexity: O(1).
        l_idx, r_idx = 0, len(matrix) - 1
        while l_idx <= r_idx:
            middle = (l_idx + r_idx) // 2
            if matrix[middle][0] <= target <= matrix[middle][-1]:
                nums = matrix[middle]
                ll_idx, rr_idx = 0, len(nums) - 1
                while ll_idx <= rr_idx:
                    n_middle = (ll_idx + rr_idx) // 2
                    if nums[n_middle] == target:
                        return True
                    elif nums[n_middle] > target:
                        rr_idx = n_middle - 1
                    else:
                        ll_idx = n_middle + 1
                return False
            elif matrix[middle][0] > target:
                r_idx = middle - 1
            else:
                l_idx = middle + 1
        return False

Solution 3:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # Approach: Flatten and Binary Search (single pass)
        # The matrix's two properties guarantee that if we read it row by row,
        # the values are strictly increasing — exactly like a sorted 1D array.
        # So we can treat it as a virtual flat array of length M*N and binary search it.
        # Map a flat index `middle` back to 2D coordinates with:
        #   row = middle // n   (e.g., index 10 in a 4×5 matrix → row 10 // 5 = 2)
        #   col = middle % n    (e.g., index 10 → col  10 %  5 = 0 → matrix[2][0])
        # Time Complexity: O(log(M * N)) — single binary search over M*N elements.
        # Space Complexity: O(1).
        n = len(matrix[0])
        l_idx, r_idx = 0, len(matrix) * n - 1
        while l_idx <= r_idx:
            middle = (l_idx + r_idx) // 2
            row = middle // n
            col = middle % n
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                r_idx = middle - 1
            else:
                l_idx = middle + 1
        return False

Conclusion

Today we searched a 2D matrix three ways, each one tightening the time complexity.

Solution 1 runs binary search independently on each row — correct, but O(M log N). It ignores the relationship between rows entirely.

Solution 2 adds a first pass to binary search for the right row before searching within it. This gives O(log M + log N) = O(log(M·N)) — two binary searches chained together.

Solution 3 is the cleanest approach: because each row's first element is greater than the previous row's last, the entire matrix is effectively one sorted sequence read left-to-right, top-to-bottom. We can binary search it directly as a flat array of M·N elements. The only trick is mapping a flat index back to 2D coordinates — row = mid // n and col = mid % n. One binary search, O(log(M·N)), no extra space.