#240

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Search a 2D Matrix II

Efficiently search for a target in a 2D matrix using binary search and matrix properties.

array binary search divide and conquer matrix

Problem Statement

Given a matrix of integers with m rows and n columns, where each row and each column is sorted in ascending order, search for a target value in this matrix. You need to determine if the target exists in the matrix and return true or false accordingly.

You must design an efficient algorithm to perform this search in a matrix that can be as large as 300x300, where the integers in the matrix are in the range from -10^9 to 10^9.

Examples

Example 1

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

Example details omitted.

Example 2

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 = 20

Output: false

Example details omitted.

Constraints

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
All the integers in each row are sorted in ascending order.
All the integers in each column are sorted in ascending order.
-109 <= target <= 109

Solution Approach

Binary Search on Rows or Columns

You can apply binary search row by row or column by column. Start from the top-right or bottom-left corner of the matrix and eliminate a row or column based on the comparison with the target.

Divide and Conquer

You can treat the matrix as a set of sub-problems and solve them recursively. By dividing the matrix into smaller sections and applying binary search over valid answer spaces, you reduce the search space efficiently.

Time Complexity Optimization

With a binary search approach, the time complexity becomes O(m + n), where m is the number of rows and n is the number of columns. This is a significant improvement over brute force searching.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on the approach chosen. A binary search per row or column leads to O(m + n) time complexity. Space complexity can be O(1) if done in-place without additional data structures.

What Interviewers Usually Probe

The candidate applies binary search efficiently and explains the trade-off between row-by-row or column-by-column binary search.
The candidate explains the divide and conquer approach in the context of the matrix.
The candidate demonstrates an understanding of time and space complexity with regard to the constraints.

Common Pitfalls or Variants

Common pitfalls

Not applying binary search correctly over the valid answer space, leading to inefficient solutions.
Failing to reduce the problem size at each step, leading to a slower solution.
Incorrectly handling edge cases such as empty rows, columns, or the target not existing in the matrix.

Follow-up variants

Optimizing the solution for larger matrices by considering different search strategies.
Handling special cases where the matrix contains duplicate values or non-standard sorts.
Adjusting the approach to search for multiple targets in the same matrix.

FAQ

What is the primary approach for solving the Search a 2D Matrix II problem?

The primary approach is to apply binary search over the valid answer space, either row by row or column by column, and reduce the search space at each step.

What is the time complexity of the binary search approach in this problem?

The time complexity is O(m + n), where m is the number of rows and n is the number of columns in the matrix.

How can GhostInterview assist with this problem?

GhostInterview provides insights into the problem's patterns, ensures candidates apply binary search correctly, and helps optimize the solution based on time and space complexity.

What are common mistakes when solving Search a 2D Matrix II?

Common mistakes include not applying binary search correctly, not reducing the search space effectively, and mishandling edge cases like missing targets.

How can I optimize my solution for larger matrices?

You can optimize your solution by carefully applying binary search per row or column and understanding the trade-offs between row-by-row versus column-by-column searches.

terminal

Solution

Solution 1: Binary Search

Since all elements in each row are sorted in ascending order, for each row, we can use binary search to find the first element greater than or equal to $\textit{target}$, and then check if that element is equal to $\textit{target}$. If it is equal to $\textit{target}$, it means the target value is found, and we return $\text{true}$. If it is not equal to $\textit{target}$, it means all elements in this row are less than $\textit{target}$, and we should continue searching the next row.

1

2

3

4

5

6

7

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            j = bisect_left(row, target)
            if j < len(matrix[0]) and row[j] == target:
                return True
        return False

Solution 2: Search from Bottom-Left or Top-Right

We start the search from the bottom-left or top-right corner and move towards the top-right or bottom-left direction. Compare the current element $\textit{matrix}[i][j]$ with $\textit{target}$:

1

2

3

4

5

6

7

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            j = bisect_left(row, target)
            if j < len(matrix[0]) and row[j] == target:
                return True
        return False

Continue Practicing

#363 max sum of rectangle no larger than k #378 kth smallest element in a sorted matrix #74 search a 2d matrix