Problem Description

You have a 2D matrix of integers with m rows and n columns that has two special properties:

1. Each row is sorted in non-decreasing order (elements go from smallest to largest or stay the same as you move from left to right)
2. The first element of each row is greater than the last element of the previous row

Your task is to determine whether a given target integer exists anywhere in this matrix. Return true if the target is found, false otherwise.

The key constraint is that your solution must run in O(log(m * n)) time complexity, which means you need to use an efficient search algorithm rather than checking every element.

For example, if you have a matrix like:

[
  [1,  3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]

And target = 3, the function should return true because 3 exists in the matrix.

If target = 13, the function should return false because 13 is not in the matrix.

The solution treats the 2D matrix as a virtual 1D sorted array by using index mapping. Since the matrix has the property that all elements are in sorted order when read row by row, we can apply binary search on this virtual array. The mapping between 1D index and 2D coordinates is done using division and modulo operations: for a 1D index i, the row is i // n and the column is i % n.

Intuition

The key observation is that the matrix has a very special structure - if you read the elements row by row from left to right, top to bottom, you get a completely sorted sequence. This is because each row is sorted, and the first element of each row is greater than the last element of the previous row.

For instance, in the matrix:

[1,  3,  5,  7]
[10, 11, 16, 20]
[23, 30, 34, 60]

Reading row by row gives us: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60] - a sorted array!

Since we need O(log(m * n)) time complexity and we're searching in what is essentially a sorted array, binary search naturally comes to mind. But how do we apply binary search on a 2D matrix?

The clever insight is that we don't need to physically convert the 2D matrix into a 1D array. Instead, we can treat it as a virtual 1D array and map between 1D indices and 2D coordinates on the fly.

If we think of the matrix as a 1D array of length m * n, then:

• Index 0 corresponds to position (0, 0) in the matrix
• Index 1 corresponds to position (0, 1) in the matrix
• Index n corresponds to position (1, 0) in the matrix (start of second row)

The mapping formula is straightforward:

• For a 1D index mid, the row number is mid // n (integer division)
• The column number is mid % n (remainder)

This allows us to perform standard binary search on the range [0, m*n-1] while accessing elements from the 2D matrix using the coordinate transformation. The beauty of this approach is that it leverages the sorted nature of the data without any preprocessing or extra space.

Learn more about Binary Search patterns.

Solution Approach

The implementation uses binary search 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
• These boundaries represent the start and end of our virtual 1D array

Binary Search Loop: The algorithm performs a standard binary search with a slight modification:

1. Calculate the middle index: mid = (left + right) >> 1 (using bit shift for division by 2)

2. Convert the 1D index to 2D coordinates using divmod(mid, n):

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

3. Compare the element at position (x, y) with the target:

   • If matrix[x][y] >= target: Move the right boundary to mid (element could be at mid or to the left)
   • If matrix[x][y] < target: Move the left boundary to mid + 1 (element must be to the right)

Finding the Target: The loop continues until left >= right, meaning we've narrowed down to a single position. This binary search variant finds the leftmost position where an element is greater than or equal to the target.

Final Check: After the loop ends, left points to the position where the target should be if it exists. We convert this 1D index back to 2D coordinates using:

• Row: left // n
• Column: left % n

Then we check if the element at this position equals the target and return the result.

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

Iteration 1:

• Calculate middle: mid = (0 + 8) >> 1 = 4
• Convert to 2D: divmod(4, 3) → row = 1, col = 1
• Check matrix[1][1] = 11
• Since 11 >= 11 (target), update right = 4
• Range becomes [0, 4]

Iteration 2:

• Calculate middle: mid = (0 + 4) >> 1 = 2
• Convert to 2D: divmod(2, 3) → row = 0, col = 2
• Check matrix[0][2] = 7
• Since 7 < 11, update left = 2 + 1 = 3
• Range becomes [3, 4]

Iteration 3:

• Calculate middle: mid = (3 + 4) >> 1 = 3
• Convert to 2D: divmod(3, 3) → row = 1, col = 0
• Check matrix[1][0] = 10
• Since 10 < 11, update left = 3 + 1 = 4
• Range becomes [4, 4]

Loop ends (left >= right)

Final Check:

• left = 4
• Convert to 2D: row = 4 // 3 = 1, col = 4 % 3 = 1
• Check matrix[1][1] = 11
• Since 11 == 11, 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──┘

Solution Implementation

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. 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, and the final return statement matrix[left // num_cols][left % num_cols] can cause an index out of bounds error if not properly handled.

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

2. Incorrect Binary Search Boundary Update

The Problem: Using right = mid - 1 instead of right = mid when matrix[row][col] >= target. This can cause the algorithm to miss the target element because the standard binary search pattern doesn't apply directly here - we're looking for the leftmost position where an element is >= target, not just any position.

Incorrect Implementation:

if matrix[row][col] >= target:
    right = mid - 1  # WRONG! This might skip over the target

Correct Implementation:

if matrix[row][col] >= target:
    right = mid  # Keep mid as a potential answer

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 or bit manipulation mid = (left + right) >> 1 with unsigned integers 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. Not Handling Duplicate Values Correctly

The Problem: While the current implementation works for finding any occurrence of the target, if you need to find a specific occurrence (first or last) of duplicate values, the boundary update logic needs adjustment.

Enhanced Solution for Finding First Occurrence:

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    if not matrix or not matrix[0]:
        return False
  
    num_rows, num_cols = len(matrix), len(matrix[0])
    left, right = 0, num_rows * num_cols - 1
    result = -1
  
    while left <= right:
        mid = (left + right) >> 1
        row, col = divmod(mid, num_cols)
      
        if matrix[row][col] == target:
            result = mid
            right = mid - 1  # Continue searching left for first occurrence
        elif matrix[row][col] < target:
            left = mid + 1
        else:
            right = mid - 1
  
    return result != -1