Problem Description

You are given a 2D integer matrix with special sorting properties and need to search for a target value in it.

The matrix has these characteristics:

• Each row is sorted in ascending order from left to right
• Each column is sorted in ascending order from top to bottom

Your task is to write an efficient algorithm that determines whether a given target value exists in the matrix. The function should return true if the target is found, and false otherwise.

For example, consider this 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]

If target = 5, the function should return true since 5 exists in the matrix. If target = 20, the function should return false since 20 does not exist in the matrix.

The challenge is to leverage the sorted properties of the matrix to create an efficient search algorithm rather than checking every element one by one.

Intuition

Since each row is sorted in ascending order, we can take advantage of this property to search more efficiently than checking every element. When we look at any single row, it's just like searching in a regular sorted array - we can use binary search!

The key insight is that we don't need to worry about the column-wise sorting property for this particular approach. We can treat the problem as searching through multiple sorted arrays (each row being one sorted array).

For each row, we can use binary search to quickly determine if the target exists in that row. Binary search allows us to find an element in a sorted array in O(log n) time instead of O(n) time for linear search.

The algorithm becomes straightforward:

1. Go through each row one by one
2. For each row, use binary search to look for the target
3. If we find the target in any row, we immediately return true
4. If we've checked all rows and haven't found the target, return false

The bisect_left function in Python performs binary search and returns the leftmost position where target should be inserted to keep the array sorted. If the element at that position equals our target, we've found it. If not, the target doesn't exist in that row.

This approach is more efficient than a naive search because instead of checking all m × n elements, we're doing m binary searches, each taking O(log n) time, giving us O(m × log n) time complexity.

Solution Approach

The solution implements a binary search approach for each row of the matrix. Here's how the implementation works:

Algorithm Steps:

1. Iterate through each row: We loop through every row in the matrix using a simple for loop.

2. Apply binary search on each row: For each row, we use Python's bisect_left function, which performs binary search. The function bisect_left(row, target) returns the leftmost index j where target should be inserted in the sorted array row to maintain sorted order.

3. Check if target is found: After getting index j from bisect_left:

   • First, we verify that j < len(matrix[0]) to ensure we're within bounds (since bisect_left could return an index equal to the array length if the target is larger than all elements)
   • Then we check if row[j] == target to confirm we've found the target value
   • If both conditions are true, we immediately return True

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

Key Implementation Details:

• bisect_left(row, target) performs binary search in O(log n) time for each row
• The boundary check j < len(matrix[0]) prevents index out of bounds errors
• Early return optimization: As soon as we find the target in any row, we return True without checking remaining rows

Time Complexity: O(m × log n) where m is the number of rows and n is the number of columns. We perform binary search (O(log n)) for each of the m rows.

Space Complexity: O(1) as we only use a constant amount of extra space for variables j and the loop iterator.

Example Walkthrough

Let's walk through a small example to illustrate the solution 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]

• Apply bisect_left([1, 3, 5, 7], 7)
• Binary search process:
  • Middle element at index 1 is 3 (3 < 7), search right half
  • Middle element at index 2 is 5 (5 < 7), search right half
  • Middle element at index 3 is 7 (7 == 7), but bisect_left returns leftmost position
• bisect_left returns index 3
• Check: Is 3 < 4 (length of row)? Yes ✓
• Check: Is row[3] == 7? Yes, 7 == 7 ✓
• Target found! Return True

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

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

• bisect_left([1, 3, 5, 7], 9) returns index 4
• Check: Is 4 < 4? No ✗
• Target not in this row, continue to next row

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

• bisect_left([2, 4, 6, 8], 9) returns index 4
• Check: Is 4 < 4? No ✗
• Target not in this row, continue to next row

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

• bisect_left([10, 11, 12, 13], 9) returns index 0
• Check: Is 0 < 4? Yes ✓
• Check: Is row[0] == 9? No, 10 ≠ 9 ✗
• Target not in this row

All rows checked, return False

This example demonstrates how binary search efficiently narrows down the search space in each row, and how the boundary checks ensure we don't access invalid indices.

Solution Implementation

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: Suboptimal Time Complexity

The current solution uses binary search on each row independently, resulting in O(m × log n) time complexity. However, this approach doesn't fully leverage the fact that columns are also sorted. We're essentially treating this as m separate sorted arrays rather than exploiting the 2D sorted structure.

Why it's problematic: For large matrices, we might unnecessarily search through many rows even when the column sorting could help us eliminate entire regions of the matrix.

Pitfall 2: Missing Early Termination Opportunities

The current approach doesn't skip rows that clearly cannot contain the target based on their range. For instance, if a row's first element is greater than the target, we still perform binary search on it.

Better Solution: Staircase Search Algorithm

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
      
        # Start from top-right corner
        row = 0
        col = len(matrix[0]) - 1
      
        while row < len(matrix) and col >= 0:
            current = matrix[row][col]
          
            if current == target:
                return True
            elif current > target:
                # Current element is too large, move left
                col -= 1
            else:
                # Current element is too small, move down
                row += 1
      
        return False

Why this is better:

• Time Complexity: O(m + n) instead of O(m × log n)
• Fully utilizes both row and column sorting properties
• Eliminates impossible regions: At each step, we eliminate either an entire row or column
• Simpler implementation: No need for binary search library

Alternative starting position: You could also start from the bottom-left corner with similar logic (moving up when current > target, right when current < target).

Pitfall 3: Not Considering Edge Cases

The original solution doesn't explicitly handle edge cases like:

• Empty matrix []
• Matrix with empty rows [[]]
• Single element matrix [[5]]

While Python's for loop naturally handles empty iterations, explicit checks make the code more robust and clear about intent.