Solution Approach

The solution implements a binary search template approach for each row of the matrix.

Binary Search Template: For each row, we search for the first index where row[mid] >= target:

left, right = 0, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if row[mid] >= target:  # feasible condition
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

Algorithm Steps:

1. Iterate through each row: We loop through every row in the matrix.

2. Apply binary search template on each row: For each row, use the template to find the first index where row[mid] >= target.

3. Check if target is found: After binary search:

   • If first_true_index != -1 and row[first_true_index] == target, we've found the target
   • Return True immediately

4. Return result: If we've searched all rows without finding the target, return False.

Key Implementation Details:

• Uses while left <= right with right = mid - 1 when feasible
• Tracks answer with first_true_index = -1 initialization
• Verifies exact match: row[first_true_index] == target

Time Complexity: O(m × log n) where m is the number of rows and n is the number of columns.

Space Complexity: O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through a small example to illustrate the binary search template approach.

Consider this 3×4 matrix and search for target = 7:

[1,  3,  5,  7]
[2,  4,  6,  8]
[10, 11, 12, 13]

Step-by-step execution:

Row 0: [1, 3, 5, 7]

• Binary search with template for first index where row[mid] >= 7:
  • left = 0, right = 3, first_true_index = -1
  • mid = 1: row[1] = 3 < 7 → left = 2
  • mid = 2: row[2] = 5 < 7 → left = 3
  • mid = 3: row[3] = 7 >= 7 → first_true_index = 3, right = 2
  • left > right, exit loop
• Check: first_true_index = 3, and row[3] = 7 == 7 ✓
• Target found! Return True

Let's see another example where target = 9 (not in matrix):

Row 0: [1, 3, 5, 7]

• Binary search with template:
  • left = 0, right = 3, first_true_index = -1
  • All elements < 9, so left keeps moving right
  • left > right, exit loop with first_true_index = -1
• first_true_index = -1, target not in this row

Row 1: [2, 4, 6, 8]

• Binary search with template:
  • All elements < 9, first_true_index = -1
• Target not in this row

Row 2: [10, 11, 12, 13]

• Binary search with template:
  • mid = 1: row[1] = 11 >= 9 → first_true_index = 1, right = 0
  • mid = 0: row[0] = 10 >= 9 → first_true_index = 0, right = -1
  • left > right, exit loop
• first_true_index = 0, but row[0] = 10 ≠ 9 ✗
• Target not in this row

All rows checked, return False

Time and Space Complexity

The time complexity is O(m × log n), where m is the number of rows and n is the number of columns in the matrix. This is because:

• The outer loop iterates through all m rows of the matrix
• For each row, bisect_left performs a binary search which takes O(log n) time (since each row has n elements)
• Therefore, the total time complexity is O(m) × O(log n) = O(m × log n)

The space complexity is O(1). The algorithm only uses a constant amount of extra space:

• The variable j stores the index returned by bisect_left
• No additional data structures are created that scale with the input size
• The iteration through the matrix doesn't require extra space proportional to the input

Common Pitfalls

Pitfall 1: Using the Wrong Binary Search Template Variant

The Issue: Using while left < right with right = mid instead of the correct template.

Incorrect Implementation:

# WRONG: Using incorrect template
while left < right:
    mid = (left + right) // 2
    if row[mid] >= target:
        right = mid
    else:
        left = mid + 1
# Returns insertion point, may be out of bounds

Correct Implementation:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if row[mid] >= target:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
# Check first_true_index != -1 before using

Pitfall 2: Not Verifying Exact Match

The Issue: The template finds the first position where row[mid] >= target, but this doesn't guarantee the value equals target.

Incorrect Implementation:

# WRONG: Assumes first_true_index always has the target
if first_true_index != -1:
    return True

Correct Implementation:

# CORRECT: Verify exact match
if first_true_index != -1 and row[first_true_index] == target:
    return True

Pitfall 3: Not Fully Leveraging 2D Sorted Structure

The binary search per row approach doesn't fully exploit the column sorting. A more optimal O(m + n) staircase approach exists:

# Start from top-right corner
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
    if matrix[row][col] == target:
        return True
    elif matrix[row][col] > target:
        col -= 1
    else:
        row += 1
return False

However, the binary search approach is still valid and demonstrates consistent template usage.

Pitfall 4: Not Handling Edge Cases

Always check for empty matrices or rows before accessing matrix[0].length.