Search a 2D Matrix LeetCode Solution [Python]

Search a 2D Matrix Leetcode problem presents an interesting challenge, and the solution relies on a clever application of binary search.

We’ll walk you through the problem, the solution, and the reasoning behind our approach.

Problem Overview

You are given a 2D matrix with two important properties:

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

Your task is to find a specific target integer in this matrix efficiently. If the target exists, return true; otherwise, return false.

Notably, you need to solve this problem in O(log(m * n)) time complexity, where m is the number of rows, and n is the number of columns.

Example:

Let’s consider an example to understand the problem better. Given the matrix:

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

And the target 3, the output should be true, as 3 is present in the matrix.

However, if the target is 13, the output should be false, as there is no 13 in the matrix.

Understanding the Constraints

Before diving into the solution, let’s dissect the problem and the constraints:

m represents the number of rows, and n represents the number of columns in the matrix.
The values in each row are sorted in ascending order, making binary search a feasible option.
The first value in each row is greater than the last value in the previous row.
You must achieve a time complexity of O(log(m * n)), which implies that a simple linear search won’t suffice.

Search a 2D Matrix LeetCode Problem Solution

1. Bruteforce Approach

One way to solve this problem is to perform a linear search, scanning each element in the 2D matrix. However, this approach would take O(m * n) time, which doesn’t meet the required time complexity.

So, let’s explore a more efficient solution.

2. Efficient Approach

We can optimize our search by leveraging the properties of the matrix. The key idea is to perform a binary search first to identify the target row efficiently.

Once we’ve found the right row, we can apply another binary search to locate the target value within that row. This approach will help us achieve the desired time complexity of O(log(m * n)).

Here’s the Python code solution for this approach:

View on GitHub ➹

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    ROWS, COLS = len(matrix), len(matrix[0])
    
    top, bottom = 0, ROWS - 1
    
    # Binary search to find the target row
    while top &lt;&equals; bottom:
        row = (top + bottom) // 2
        
        if target > matrix[row][-1]:
            top = row + 1
        elif target &lt; matrix[row][0]:
            bottom = row - 1
        else:
            break
    
    if not (top &lt;&equals; bottom):
        return False
    
    # Binary search to find the target in the row
    row = (top + bottom) // 2
    left, right = 0, COLS - 1
    
    while left &lt;&equals; right:
        mid = (left + right) // 2
        
        if target > matrix[row][mid]:
            left = mid + 1
        elif target &lt; matrix[row][mid]:
            right = mid - 1
        else:
            return True
    
    return False

Time and Space Complexity

Now, let’s discuss the time and space complexity of our efficient solution:

Time Complexity: O(log(m) + log(n)) – This is because we perform two binary searches, one to find the target row and another to find the target within that row. Both binary searches operate in logarithmic time.
Space Complexity: O(1) – We use a constant amount of additional space to store variables, making the space complexity very efficient.

Reasoning Behind Our Approach

Our approach is highly efficient due to the properties of the matrix:

Rows are sorted, allowing us to use binary search to find the correct row efficiently.
The first element in each row is greater than the last element in the previous row, which helps us determine whether to search above or below a particular row.

By combining these properties and leveraging binary search, we achieve a time complexity that meets the problem’s requirements.

Conclusion

In this blog post, we’ve tackled the “Search a 2D Matrix” problem from LeetCode.

We’ve provided an efficient Python solution that leverages binary search to locate a target value in a sorted 2D matrix.

Understanding the problem’s properties is crucial to crafting an effective solution. We hope this post has been helpful to you.

If you have any questions, or suggestions, or want to share your thoughts, feel free to comment below.

Additionally, if you found this content useful, please consider sharing it with others who might benefit from it.

Access the LeetCode problem here.

Happy coding!