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

What Is LeetCode 240: Search a 2D Matrix II?

In LeetCode 240: Search a 2D Matrix II, you’re given a 2D matrix where each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Your task is to determine if a given target value exists in the matrix. Unlike array traversal problems like LeetCode 238: Product of Array Except Self, this one leverages the matrix’s sorted properties for efficiency.

Problem Statement

• Input: A 2D integer matrix matrix and an integer target.
• Output: A boolean—true if target is in the matrix, false otherwise.
• Rules: Use the sorted nature of rows and columns to optimize the search.

Constraints

• Matrix dimensions: m rows (1 to 300), n columns (1 to 300).
• Values: -10^9 to 10^9.
• Rows and columns are sorted in ascending order.

Examples

• 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 (5 is in the matrix).

• Output: false (20 isn’t present).

• Output: true.

Understanding the Problem: Searching a Sorted Matrix

To solve LeetCode 240: Search a 2D Matrix II in Python, we need to locate a target value in a matrix where rows and columns are sorted. A naive approach—checking every cell—takes O(mn) time, which is too slow for large matrices. Instead, we’ll use the sorted structure to our advantage with two methods: 1. Best Solution (Top-Right Search): O(m + n) time, O(1) space—smart and fast. 2. Alternative Solution (Binary Search per Row)*: O(m * log n) time, O(1) space—systematic but slower.

Let’s start with the best solution.

Best Solution: Top-Right Search Approach

Why This Is the Best Solution

The top-right search approach is the star of LeetCode 240 because it exploits the matrix’s sorted properties to achieve O(m + n) time complexity with no extra space. Starting from the top-right corner, it eliminates entire rows or columns with each step, making it both efficient and intuitive.

How It Works

• Begin at the top-right corner (row = 0, col = n-1).
• Compare the current element with the target:
• If it equals the target, return true.
• If it’s greater, move left (eliminate the column).
• If it’s less, move down (eliminate the row).
• Continue until you find the target or exit the matrix bounds.

Step-by-Step Example

Example: matrix = [[1,4,7], [2,5,8], [3,6,9]], target = 5

• Start: Top-right, row = 0, col = 2, value = 7.
• 7 > 5, move left to col = 1, value = 4.
• Next: row = 0, col = 1, value = 4.
• 4 < 5, move down to row = 1, value = 5.
• Next: row = 1, col = 1, value = 5.
• 5 = 5, found it! Return true.

Example: Same matrix, target = 10

• Start: row = 0, col = 2, value = 7.
• 7 < 10, move down to row = 1, value = 8.
• Next: row = 1, col = 2, value = 8.
• 8 < 10, move down to row = 2, value = 9.
• Next: row = 2, col = 2, value = 9.
• 9 < 10, move down, row = 3—out of bounds. Return false.

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # Step 1: Check if matrix is empty
        if not matrix or not matrix[0]:
            return False

        # Step 2: Set starting point at top-right
        m, n = len(matrix), len(matrix[0])
        row, col = 0, n - 1

        # Step 3: Search while within bounds
        while row < m and col >= 0:
            current = matrix[row][col]
            # Step 4: Compare with target
            if current == target:
                return True
            elif current > target:
                col -= 1  # Move left
            else:
                row += 1  # Move down

        # Step 5: Target not found
        return False

• Time Complexity: O(m + n)—we move at most m steps down and n steps left.
• Space Complexity: O(1)—no extra space needed.

This method’s simplicity and speed make it a winner.

Alternative Solution: Binary Search per Row

Why an Alternative Approach?

The binary search per row method is a solid alternative for LeetCode 240. It applies binary search to each row, leveraging the row-wise sorting to find the target. It’s more systematic and easier to grasp for those familiar with binary search, though it’s less efficient than the top-right approach.

How It Works

• For each row in the matrix:
• Perform a binary search to check if the target exists.
• Return true if found in any row, false otherwise.

Step-by-Step Example

Example: matrix = [[1,4,7], [2,5,8], [3,6,9]], target = 5

• Row 0: [1,4,7]
• Binary search: Mid = 4, 4 < 5, check [7], not found.
• Row 1: [2,5,8]
• Binary search: Mid = 5, 5 = 5, found! Return true.
• Stop: No need to check further.

Code for Binary Search Approach

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # Step 1: Check if matrix is empty
        if not matrix or not matrix[0]:
            return False

        # Step 2: Binary search helper function
        def binary_search(row, target):
            left, right = 0, len(row) - 1
            while left <= right:
                mid = (left + right) // 2
                if row[mid] == target:
                    return True
                elif row[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return False

        # Step 3: Apply binary search to each row
        for row in matrix:
            if binary_search(row, target):
                return True

        # Step 4: Target not found
        return False

• Time Complexity: O(m * log n)—binary search on m rows of length n.
• Space Complexity: O(1)—no extra space beyond variables.

It’s reliable but takes more steps than the best solution.

Comparing the Two Solutions

• Best Solution (Top-Right Search):
• Pros: O(m + n) time, minimal space, elegant.
• Cons: Less familiar to some beginners.
• Alternative Solution (Binary Search):
• Pros: Uses familiar binary search, straightforward.
• Cons: O(m * log n) time, slower for large matrices.

The top-right search stands out for its efficiency.

Additional Examples and Edge Cases

Single Cell

• Input: [[1]], target = 1
• Output: true

All Same

• Input: [[5,5], [5,5]], target = 5
• Output: true

Negative Numbers

• Input: [[-1,0], [-2,-1]], target = -2
• Output: true

Both solutions handle these gracefully.

Complexity Breakdown

• Top-Right Search:
• Time: O(m + n)—linear and fast.
• Space: O(1)—super lean.
• Binary Search:
• Time: O(m * log n)—logarithmic per row.
• Space: O(1)—still minimal.

The top-right method wins on speed.

Key Takeaways for Beginners

• Sorted Matrix: Use row and column order to cut search time.
• Top-Right Trick: Eliminates rows or columns efficiently.
• Binary Search: Great tool, but slower here.
• Python Tip: Master list indexing—see [Python Basics](/python/basics).

Final Thoughts: Search Like a Matrix Master

LeetCode 240: Search a 2D Matrix II in Python is a fantastic challenge to hone your search skills. The top-right search dazzles with O(m + n) efficiency, while binary search offers a familiar fallback. Want more matrix fun? Try LeetCode 74: Search a 2D Matrix or LeetCode 378: Kth Smallest Element in a Sorted Matrix. Ready to hunt? Head to Solve LeetCode 240 on LeetCode and track down those targets today!