How do you solve Search a 2D Matrix on LeetCode?

Search a 2D Matrix (LeetCode #74) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log(m * n)) time complexity and O(1) space complexity. Key insight: The matrix is sorted both row-wise and column-wise, allowing for efficient searching.

What is the brute force solution for Search a 2D Matrix?

The brute force approach for Search a 2D Matrix is Brute Force, with O(m * n) time complexity and O(1) space complexity. The simplest way to find the target is to check every element in the matrix one by one. Since each row is sorted, we can iterate through each row and check if the target exists. The optimal Optimal Solution approach improves this to O(log(m * n)).

What algorithm or data structure is used to solve Search a 2D Matrix?

Search a 2D Matrix uses the following concepts: Array, Binary Search, Matrix. The recommended patterns to study are: Binary Search, Matrix Search.

What are the interview tips for Search a 2D Matrix?

Always clarify the constraints and properties of the input data before diving into coding. Explain your thought process while coding to showcase your understanding. Practice converting between 1D and 2D indices to avoid confusion during implementation.

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

Not converting the mid index correctly to 2D coordinates. Forgetting to check if the matrix is empty before proceeding with the search.

#74

Search a 2D Matrix

Medium

ArrayBinary SearchMatrixBinary SearchMatrix Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(m * n)	O(log(m * n))
Space	O(1)	O(1)

💡

Intuition

Time O(log(m * n))Space O(1)

Since the matrix is sorted in a specific way, we can treat it as a single sorted array and use binary search to find the target efficiently.

⚙️

Algorithm

7 steps

1Step 1: Initialize two pointers, left at 0 and right at m * n - 1 (total number of elements - 1).
2Step 2: While left <= right, calculate the mid index as (left + right) // 2.
3Step 3: Convert mid index to 2D coordinates: row = mid // n and col = mid % n.
4Step 4: If matrix[row][col] equals target, return true.
5Step 5: If matrix[row][col] is less than target, move left pointer to mid + 1.
6Step 6: If matrix[row][col] is greater than target, move right pointer to mid - 1.
7Step 7: If the loop ends, return false.

solution.py15 lines

1def searchMatrix(matrix, target):
2    if not matrix:
3        return False
4    m, n = len(matrix), len(matrix[0])
5    left, right = 0, m * n - 1
6    while left <= right:
7        mid = (left + right) // 2
8        mid_val = matrix[mid // n][mid % n]
9        if mid_val == target:
10            return True
11        elif mid_val < target:
12            left = mid + 1
13        else:
14            right = mid - 1
15    return False

ℹ

Complexity note: This complexity is achieved by treating the matrix as a flat array and applying binary search, which reduces the search space logarithmically.

1The matrix is sorted both row-wise and column-wise, allowing for efficient searching.
2Binary search can be applied in a 2D context by treating the matrix as a single sorted array.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.