Solution Approach

The solution implements the two binary search approach mentioned in the reference. Let's break down the implementation step by step:

1. Define the counting function:

def count(x):
    return sum(bisect_right(row, x) for row in grid)

This helper function counts how many elements in the entire matrix are less than or equal to x. For each row, bisect_right(row, x) returns the rightmost position where we can insert x to keep the row sorted, which effectively gives us the count of elements ≤ x in that row. We sum these counts across all rows.

2. Calculate the target position:

m, n = len(grid), len(grid[0])
target = (m * n + 1) >> 1

Since we have an odd number of elements, the median is at position ⌈(m × n) / 2⌉. The expression (m * n + 1) >> 1 is equivalent to (m * n + 1) // 2, which gives us the ceiling of (m × n) / 2 for odd numbers.

3. Perform binary search using the template:

We define our feasible function: feasible(x) = count(x) >= target. This creates a pattern like [false, false, ..., true, true, ...] as x increases. We want to find the first true value (the smallest x where count >= target).

Using the standard binary search template:

left, right = 0, 10**6
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if count(mid) >= target:  # Feasible
        first_true_index = mid
        right = mid - 1  # Try to find smaller value
    else:
        left = mid + 1

return first_true_index

The template finds the smallest value x such that count(x) >= target, which is exactly our median value.

Time Complexity:

• Outer binary search: O(log(range)) where range is the value range (10^6 in this case)
• For each binary search iteration, we call count(x) which performs m binary searches, each taking O(log n) time
• Total: O(m × log(n) × log(range))

This is significantly better than the naive O(m × n × log(m × n)) approach of merging and sorting all elements.

Example Walkthrough

Let's walk through finding the median of this 3×3 matrix:

grid = [[1, 1, 2],
        [2, 3, 3],
        [1, 3, 4]]

Step 1: Setup

• Matrix dimensions: m = 3, n = 3
• Total elements: 3 × 3 = 9 (odd number)
• Target position: (9 + 1) >> 1 = 5 (we need the 5th smallest element)
• Feasible function: count(x) >= 5

Step 2: Binary Search using Template

Initialize: left = 0, right = 10^6, first_true_index = -1

(After many iterations narrowing down, we focus on the key iterations)

Key Iteration: left = 1, right = 4

• mid = (1 + 4) // 2 = 2
• Count elements ≤ 2:
  • Row 1: [1, 1, 2] → bisect_right gives 3 (all elements ≤ 2)
  • Row 2: [2, 3, 3] → bisect_right gives 1 (only first element ≤ 2)
  • Row 3: [1, 3, 4] → bisect_right gives 1 (only first element ≤ 2)
  • Total count = 3 + 1 + 1 = 5 >= 5 → feasible!
• Update first_true_index = 2, right = mid - 1 = 1

Next Iteration: left = 1, right = 1

• mid = (1 + 1) // 2 = 1
• Count elements ≤ 1:
  • Row 1: [1, 1, 2] → bisect_right gives 2
  • Row 2: [2, 3, 3] → bisect_right gives 0
  • Row 3: [1, 3, 4] → bisect_right gives 1
  • Total count = 2 + 0 + 1 = 3 < 5 → not feasible
• Update left = mid + 1 = 2

Final: left = 2, right = 1

• left > right, loop terminates
• Result: first_true_index = 2

Step 3: Result

The binary search finds that 2 is the smallest value where at least 5 elements are ≤ to it. Therefore, the median is 2.

To verify: Sorting all elements gives [1, 1, 1, 2, 2, 3, 3, 3, 4], and the 5th element is indeed 2.

The key insight is that we never actually sorted all elements. Instead, we efficiently searched for the value that would be at the median position by counting how many elements are less than or equal to candidate values.

Time and Space Complexity

The time complexity is O(m × log n × log M), where m is the number of rows, n is the number of columns of the grid, and M is the maximum element in the grid (here M = 10^6).

Breaking down the complexity:

• The outer binary search using bisect_left on the range [0, 10^6] performs O(log M) iterations
• For each iteration, the count function is called
• Inside count, we iterate through m rows
• For each row, bisect_right performs binary search on a sorted row of length n, taking O(log n) time
• Therefore, each count call takes O(m × log n) time
• Total time complexity: O(log M × m × log n) = O(m × log n × log M)

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for variables like m, n, and target. The bisect_left function with range(10^6 + 1) doesn't actually create the full range in memory due to Python's lazy evaluation of range objects.

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

Common Pitfalls

1. Using Wrong Binary Search Template

The Pitfall: Using while left < right with right = mid instead of the standard template with while left <= right, first_true_index, and right = mid - 1.

Why It's Wrong: Different binary search variants behave differently at boundaries. Using inconsistent patterns makes code harder to reason about and more prone to off-by-one errors.

The Fix: Use the standard template consistently:

left, right = 0, 10**6
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if count(mid) >= target:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index

2. Incorrect Value Range Assumption

The code assumes all matrix values are between 0 and 10^6, which may not always be true. If the matrix contains negative numbers or values larger than 10^6, the binary search will fail to find the correct median.

Solution: Find the actual min and max values in the matrix:

min_val = min(row[0] for row in grid)
max_val = max(row[-1] for row in grid)
left, right = min_val, max_val

3. Confusion Between Element Count and Element Value

A common mistake is confusing what the binary search returns. We're searching through a range of values with a counting function. The result is the actual median value, not an index into the matrix.

4. Off-by-One Error in Median Position Calculation

When calculating the median position, using (m * n + 1) // 2 vs (m * n) // 2 can lead to different results. The current formula works for odd-sized matrices but would need adjustment for even sizes.

Solution for odd matrices (current problem):

median_position = (m * n + 1) // 2