Solution Approach

The implementation uses the standard binary search template on a virtual 1D array representation of the 2D matrix. Here's how the algorithm works step by step:

Initial Setup:

• Get the dimensions: m (number of rows) and n (number of columns)
• Set binary search boundaries: left = 0 and right = m * n - 1
• Initialize first_true_index = -1 to track the first position where element >= target

Feasible Function: For any index mid, the feasible condition is: matrix[mid // n][mid % n] >= target

This creates a pattern like [false, false, false, true, true, true] where we want to find the first true.

Binary Search Loop: Using while left <= right:

1. Calculate the middle index: mid = (left + right) // 2

2. Convert the 1D index to 2D coordinates:

   • row = mid // n gives us the row index
   • col = mid % n gives us the column index

3. Check if feasible (element >= target):

   • If matrix[row][col] >= target: Record first_true_index = mid, then search left with right = mid - 1
   • If matrix[row][col] < target: Search right with left = mid + 1

Final Check: After the loop, first_true_index holds the position of the first element >= target. We check if that element equals the target:

• If first_true_index == -1, the target is larger than all elements, return false
• Otherwise, convert to 2D coordinates and check if matrix[first_true_index // n][first_true_index % n] == target

Time Complexity: O(log(m * n)) - We perform binary search on m * n elements Space Complexity: O(1) - Only using a few variables for indices and coordinates

The elegance of this solution lies in treating the 2D matrix as a 1D sorted array without actually reshaping it, achieving optimal time complexity while maintaining constant space usage.

Example Walkthrough

Let's walk through searching for target = 11 in this matrix:

[
  [1,  4,  7],
  [10, 11, 13],
  [15, 18, 21]
]

Setup:

• Matrix dimensions: m = 3 rows, n = 3 columns
• Virtual 1D array has 3 * 3 = 9 elements
• Binary search range: left = 0, right = 8
• first_true_index = -1
• Feasible condition: matrix[mid // 3][mid % 3] >= 11

Iteration 1:

• left = 0, right = 8
• Calculate middle: mid = (0 + 8) // 2 = 4
• Convert to 2D: row = 1, col = 1
• Check matrix[1][1] = 11 >= 11? Yes (feasible)
• Update first_true_index = 4, right = mid - 1 = 3

Iteration 2:

• left = 0, right = 3
• Calculate middle: mid = (0 + 3) // 2 = 1
• Convert to 2D: row = 0, col = 1
• Check matrix[0][1] = 4 >= 11? No
• Update left = mid + 1 = 2

Iteration 3:

• left = 2, right = 3
• Calculate middle: mid = (2 + 3) // 2 = 2
• Convert to 2D: row = 0, col = 2
• Check matrix[0][2] = 7 >= 11? No
• Update left = mid + 1 = 3

Iteration 4:

• left = 3, right = 3
• Calculate middle: mid = (3 + 3) // 2 = 3
• Convert to 2D: row = 1, col = 0
• Check matrix[1][0] = 10 >= 11? No
• Update left = mid + 1 = 4

Loop ends (left > right)

Final Check:

• first_true_index = 4
• Convert to 2D: row = 4 // 3 = 1, col = 4 % 3 = 1
• Check matrix[1][1] = 11 == 11? Yes
• Return true

The virtual 1D array mapping works as follows:

Index: 0  1  2  3   4   5   6   7   8
Value: 1  4  7  10  11  13  15  18  21
       └─row 0─┘└──row 1──┘└──row 2──┘

Time and Space Complexity

The time complexity is O(log(m × n)), where m is the number of rows and n is the number of columns in the matrix. This is because the algorithm performs binary search on a virtual flattened array of size m × n. Binary search divides the search space in half with each iteration, resulting in logarithmic time complexity relative to the total number of elements.

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for variables (left, right, mid, x, y) regardless of the input size. No additional data structures are created that scale with the input.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

The Problem: Using while left < right with right = mid instead of the standard template. This alternative variant works but is harder to reason about and inconsistent with the canonical pattern.

Incorrect Implementation:

while left < right:
    mid = (left + right) // 2
    if matrix[row][col] >= target:
        right = mid  # Wrong variant!
    else:
        left = mid + 1
return matrix[left // cols][left % cols] == target

Correct Template Implementation:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if matrix[row][col] >= target:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index != -1 and matrix[...] == target

2. Index Out of Bounds Error

The Problem: The most common pitfall occurs when the matrix is empty or has empty rows. The code len(matrix[0]) will throw an IndexError if the matrix is empty.

Example Case:

• Empty matrix: matrix = []
• Matrix with empty rows: matrix = [[]]

Solution: Add validation checks at the beginning of the function:

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    # Handle edge cases
    if not matrix or not matrix[0]:
        return False

    num_rows, num_cols = len(matrix), len(matrix[0])
    # ... rest of the code

3. Integer Overflow in Different Languages

The Problem: While Python handles large integers automatically, if you're implementing this in languages like Java or C++, calculating mid = (left + right) / 2 can cause integer overflow when left and right are large.

Solution for Other Languages: Use mid = left + (right - left) / 2 to avoid overflow.

4. Confusion Between Row-Major and Column-Major Ordering

The Problem: Incorrectly mapping between 1D and 2D indices by swapping the division and modulo operations. This happens when developers confuse row-major ordering (used here) with column-major ordering.

Wrong Mapping:

row, col = divmod(mid, num_rows)  # WRONG! Should divide by num_cols

Correct Mapping:

row, col = divmod(mid, num_cols)  # Correct: row = mid // num_cols, col = mid % num_cols

5. Forgetting to Check if first_true_index is -1

The Problem: When using the template, if first_true_index is never updated (target is larger than all elements), accessing matrix[first_true_index // cols][...] will cause an error.

Solution: Always check for the -1 case:

if first_true_index == -1:
    return False
row, col = divmod(first_true_index, num_cols)
return matrix[row][col] == target