LeetCode 74: Search a 2D Matrix Solution in Python – A Step-by-Step Guide

What Is LeetCode 74: Search a 2D Matrix?

In LeetCode 74: Search a 2D Matrix, you’re given a 2D matrix matrix and an integer target. Your task is to determine if target exists in the matrix, returning True if it does, False if it doesn’t. The matrix has unique properties:

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

This makes the matrix behave like a flattened, sorted 1D array. For example, with matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]] and target = 3, the answer is True because 3 is in the first row.

Problem Statement

• Input: A 2D integer array matrix and an integer target.
• Output: A boolean—True if target is in the matrix, False otherwise.
• Rules:
• Matrix follows the sorted properties above.
• Search must be efficient (implied by problem context).

Constraints

• 1 <= m, n <= 100 (m rows, n columns)
• -10⁴ <= matrix[i][j], target <= 10⁴

Examples

• Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3
• Output: True
• Why: 3 is at matrix[0][1].
• Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 13
• Output: False
• Why: 13 isn’t in the matrix.
• Input: matrix = [[1]], target = 1
• Output: True
• Why: Single-element matrix contains 1.

Understanding the Problem: Searching the Sorted Grid

To solve LeetCode 74: Search a 2D Matrix in Python, we need to find target in a matrix that’s secretly a sorted 1D array in disguise. A naive approach—scanning every element—takes O(m*n) time, which is fine but not great for up to 100x100 elements. Since the matrix is sorted, we can do better with binary search. We’ll explore:

• Best Solution (Single Binary Search): O(log(m*n)) time, O(1) space—treats the matrix as 1D.
• Alternative Solution (Two-Step Binary Search): O(log m + log n) time, O(1) space—finds row, then column.

Let’s start with the Best Solution—a single binary search—and break it down clearly.

Best Solution: Single Binary Search with Matrix-to-1D Mapping

Why This Is the Best Solution

The single binary search approach is tops because it’s both fast—O(log(m*n)) time—and lean—O(1) space. By treating the 2D matrix as a virtual 1D array, it leverages the sorted property in one clean sweep. No extra steps, no fuss—just a clever mapping from 1D indices to 2D coordinates. It’s like flattening the grid in your mind and searching it with laser precision!

How It Works

Here’s the strategy:

• Step 1: Understand the Mapping:
• A matrix with m rows and n columns has m*n elements.
• For a 1D index mid, the 2D coordinates are:
• Row = mid // n (integer division by columns).
• Col = mid % n (remainder gives column).
• Step 2: Binary Search:
• Set left = 0, right = m*n - 1.
• Compute mid, map to matrix[mid // n][mid % n].
• Compare with target:
• Equal? Return True.
• Too big? Move right = mid - 1.
• Too small? Move left = mid + 1.
• Step 3: Finish:
• If loop ends, target isn’t there—return False.

Step-by-Step Example

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

• Setup: m = 3, n = 4, total elements = 12.
• left = 0, right = 11:
• mid = (0 + 11) // 2 = 5.
• row = 5 // 4 = 1, col = 5 % 4 = 1 → matrix[1][1] = 11.
• 11 > 3 → right = 4.
• left = 0, right = 4:
• mid = (0 + 4) // 2 = 2.
• row = 2 // 4 = 0, col = 2 % 4 = 2 → matrix[0][2] = 5.
• 5 > 3 → right = 1.
• left = 0, right = 1:
• mid = (0 + 1) // 2 = 0.
• row = 0 // 4 = 0, col = 0 % 4 = 0 → matrix[0][0] = 1.
• 1 < 3 → left = 1.
• left = 1, right = 1:
• mid = (1 + 1) // 2 = 1.
• row = 1 // 4 = 0, col = 1 % 4 = 1 → matrix[0][1] = 3.
• 3 == 3 → Return True.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained step-by-step:

Copy codeclass Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # Step 1: Get dimensions
        m = len(matrix)
        n = len(matrix[0])

        # Step 2: Binary search setup
        left = 0
        right = m * n - 1

        # Step 3: Perform binary search
        while left <= right:
            mid = (left + right) // 2
            # Map 1D index to 2D coordinates
            row = mid // n
            col = mid % n
            value = matrix[row][col]

            if value == target:
                return True
            elif value < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

• Line 4-5: Get m (rows) and n (columns).
• Line 8-9: Set search bounds for 0 to m*n - 1.
• Line 12-22: Binary search loop:
• Line 13: Compute middle index.
• Line 15-16: Convert mid to row and col.
• Line 17: Get value at that position.
• Line 19: Found target, return True.
• Line 21: Value too small, search right half.
• Line 23: Value too big, search left half.
• Line 25: Target not found, return False.
• Time Complexity: O(log(m*n))—binary search on virtual 1D array.
• Space Complexity: O(1)—no extra space.

This is like unrolling the matrix into a single line and slicing through it!

Alternative Solution: Two-Step Binary Search

Why an Alternative Approach?

The two-step binary search splits the problem into two phases—finding the right row, then the right column—running in O(log m + log n) time with O(1) space. It’s a bit more intuitive for some, breaking the task into manageable chunks. It’s like first picking the right shelf, then the right book—methodical and clear!

How It Works

Here’s the plan:

• Step 1: Find the Row:
• Binary search the first column to find the row where target could be (last row where matrix[row][0] <= target).
• Step 2: Search the Row:
• Binary search that row to find target.
• Step 3: Result:
• Return True if found, False otherwise.

Step-by-Step Example

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

• Step 1: Row Search (first column: [1, 10, 23]):
• left = 0, right = 2:
• mid = 1, matrix[1][0] = 10 > 3 → right = 0.
• left = 0, right = 0:
• mid = 0, matrix[0][0] = 1 <= 3 → Row = 0.
• Step 2: Column Search ([1, 3, 5, 7]):
• left = 0, right = 3:
• mid = 1, matrix[0][1] = 3 == 3 → Return True.

Code for Two-Step Approach

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

        # Step 1: Binary search to find row
        left, right = 0, m - 1
        while left <= right:
            mid = (left + right) // 2
            if matrix[mid][0] == target:
                return True
            elif matrix[mid][0] < target:
                left = mid + 1
            else:
                right = mid - 1
        row = right if right >= 0 else 0  # Last row where start <= target

        # Step 2: Binary search in the row
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if matrix[row][mid] == target:
                return True
            elif matrix[row][mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

• Line 7-15: Search first column for row.
• Line 16: Pick row (adjust if right goes negative).
• Line 19-27: Search selected row.
• Time Complexity: O(log m + log n)—two separate binary searches.
• Space Complexity: O(1).

It’s a two-part treasure hunt!

Comparing the Two Solutions

• Single Binary Search (Best):
• Pros: O(log(m*n)), O(1), one clean search.
• Cons: Mapping might feel abstract.
• Two-Step Binary Search (Alternative):
• Pros: O(log m + log n), O(1), intuitive steps.
• Cons: Slightly more code, two phases.

Single search is simpler and just as fast.

Additional Examples and Edge Cases

• [[1, 2]], target = 2: True.
• [[1], [3]], target = 2: False.
• [[1, 3]], target = 1: True.

Both handle these perfectly.

Complexity Breakdown

• Single Binary Search: Time O(log(m*n)), Space O(1).
• Two-Step Binary Search: Time O(log m + log n), Space O(1).

Both are logarithmic, but single is more unified.

Key Takeaways

• Single Binary Search: Flatten and conquer!
• Two-Step: Row first, then column!
• Sorted Property: The key to speed.
• Python Tip: Integer division rocks—see [Python Basics](/python/basics).

Final Thoughts: Find Your Target

LeetCode 74: Search a 2D Matrix in Python is a sorted search delight. The single binary search cuts through with elegance, while the two-step approach offers clarity. Want more binary search fun? Try LeetCode 33: Search in Rotated Sorted Array or LeetCode 153: Find Minimum in Rotated Sorted Array. Ready to search? Head to Solve LeetCode 74 on LeetCode and track down that target today!