Median in a Row-Wise Sorted Matrix

1. Problem Statement & Overview

When given an $N \times M$ 2D matrix where both $N$ and $M$ are odd integers, every individual row is sorted in non-decreasing order. The product of two odd numbers is always odd ($Odd \times Odd = Odd$), which guarantees that the total number of elements ($N \times M$) in the matrix is an odd integer.

The objective is to find and return the median of all the elements in the 2D matrix.

• Definition of Median: The middle value in a sorted set of numbers such that the number of elements strictly smaller than it is balanced equally on both sides.
• Example Scenario: For an $N = 3, M = 5$ matrix, the total number of elements is $15$. The median will sit at the index $7$ (0-indexed) when all elements are arranged in a flat, sorted 1D array, having exactly $7$ elements on its left and $7$ elements on its right.

2. The Naive (Brute Force) Approach & Its Limitations

Before designing an optimized solution, an intuitive brute-force approach can be evaluated.

Step-by-Step Brute Force Strategy

1. Flattening: Traverse through every row and column of the 2D matrix and copy each element into an unsorted 1D list/array.
2. Sorting: Apply a standard sorting algorithm (e.g., Dual-Pivot Quicksort or Merge Sort) on the 1D array.
3. Extraction: Retrieve the median element located at the exact middle index: $\lfloor \frac{N \times M}{2} \rfloor$.

Brute Force Pseudocode

def findMedian(matrix, n, m):
    flat_list = []
    # Step 1: Flatten 2D matrix into 1D list
    for i in range(n):
        for j in range(m):
            flat_list.append(matrix[i][j])
            
    # Step 2: Sort the 1D list
    flat_list.sort()
    
    # Step 3: Return middle element
    median_index = (n * m) // 2
    return flat_list[median_index]

Complexity Analysis

• Time Complexity: $\mathcal{O}(N \times M + (N \times M) \log(N \times M))$
  • $\mathcal{O}(N \times M)$ to traverse and collect all elements.
  • $\mathcal{O}((N \times M) \log(N \times M))$ to sort the total elements.
• Space Complexity: $\mathcal{O}(N \times M)$ to store elements in the temporary 1D list.
• Interviewer Feedback: This approach fails to leverage the property that individual rows are already sorted. The extra logarithmic sorting factor and space overhead make it unacceptable for rigorous coding interviews.

3. Core Mental Model: Binary Search on Answer Space

To optimize below $\mathcal{O}((N \times M) \log(N \times M))$, we cannot afford to explicitly touch or sort every single element individually. Instead, we can apply Binary Search on the Answer Space.

Real-Life Analogy

Imagine guessing a hidden number between $1$ and $16$. Instead of checking every single number one by one, you guess the middle number ($8$), ask an oracle how many numbers in the matrix are less than or equal to $8$, and intelligently eliminate half of your search space depending on whether the count is too high or too low.

Establishing the Search Space

• Minimum Possible Answer (low): The smallest element in the entire matrix. Because every row is sorted, the minimum element must reside in the very first column: $\text{matrix}[i][0]$ across all rows. For safety, we can initialize low = 1 or the absolute minimum value in the matrix.
• Maximum Possible Answer (high): The largest element in the matrix, typically bounded by the constraints (e.g., $10^9$) or found in the last column: $\text{matrix}[i][M - 1]$.

4. Visualizing the Frequency Count Property

To drive binary search, we need a helper function (black box) that answers:

"How many elements in the entire 2D matrix are less than or equal to a given number $X$?"

Let us trace how elements smaller than or equal to a target candidate accumulate across rows:

Binary Search Decision Rule

In a matrix of size $N \times M$ with total elements $T = N \times M$, the median requires exactly $\text{required} = \lfloor \frac{T}{2} \rfloor$ elements to be strictly smaller than or equal to it.

• If $\text{count}(\text{mid}) \le \text{required}$: It means mid is too small or not high enough to be the median. We must search for a larger value by moving low = mid + 1.
• If $\text{count}(\text{mid}) > \text{required}$: It means mid has too many elements smaller than or equal to it. It could potentially be our answer, but we need to check if a tighter valid boundary exists on the left by moving high = mid - 1.

5. Step-by-Step Binary Search Walkthrough

Let's walk through the binary search process using our search range $[1, 16]$ with a required smaller count of $7$ elements:

6. Optimizing the Black Box via Upper Bound

Computing how many elements are smaller than or equal to $X$ without scanning every element is achieved by leveraging the fact that each row is already sorted.

Utilizing Upper Bound

For any given row (which is a sorted 1D array), we can use the Upper Bound algorithm.

• Upper Bound returns the iterator or index of the first element strictly greater than $X$.
• The index of this first element greater than $X$ directly tells us how many elements in that row are less than or equal to $X$.

For instance, if Upper Bound on a row of length $5$ returns index $3$, it implies that elements at indices $0, 1,$ and $2$ (total of $3$ elements) are less than or equal to $X$.

Black Box Implementation Pseudocode

# Helper function: Standard Upper Bound in a sorted array
def upperBound(arr, x):
    low = 0
    high = len(arr) - 1
    ans = len(arr)
    
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] > x:
            ans = mid      # Possible answer, look further left
            high = mid - 1
        else:
            low = mid + 1  # Look on the right
            
    return ans

# Black Box: Count elements <= x across all rows
def countSmallerThanEqualTo(matrix, n, m, x):
    cnt = 0
    for i in range(n):
        cnt += upperBound(matrix[i], x)
    return cnt

7. Complete Solution Implementation

Here is the complete, cohesive implementation combining Binary Search on the answer space with row-wise Upper Bound counting:

class Solution:
    def upperBound(self, arr, x):
        low = 0
        high = len(arr) - 1
        ans = len(arr)
        
        while low <= high:
            mid = (low + high) // 2
            if arr[mid] > x:
                ans = mid
                high = mid - 1
            else:
                low = mid + 1
        return ans

    def countSmallerThanEqualTo(self, matrix, n, m, x):
        cnt = 0
        for i in range(n):
            cnt += self.upperBound(matrix[i], x)
        return cnt

    def findMedian(self, matrix):
        n = len(matrix)
        m = len(matrix[0])
        
        # Define search space for values in the matrix
        low = 1
        high = 10**9  # Standard constraint bound for element values
        
        required = (n * m) // 2
        ans = -1
        
        while low <= high:
            mid = (low + high) // 2
            
            # Count elements <= mid across all rows
            smaller_equals = self.countSmallerThanEqualTo(matrix, n, m, mid)
            
            if smaller_equals <= required:
                low = mid + 1  # Need more elements, search right
            else:
                ans = mid      # Valid candidate, try finding a smaller valid value
                high = mid - 1
                
        return low

8. Complexity Analysis Summary

Complexity Breakdown for Optimized Approach:

• Search Space Range: Let $\text{Max}$ and $\text{Min}$ be the maximum and minimum possible element values. The binary search runs $\log(\text{Max} - \text{Min})$ iterations (bounded by $\log_2(10^9) \approx 30$ steps).
• Black Box Cost: In each binary search step, we iterate through all $N$ rows and perform a binary search (Upper Bound) of time complexity $\mathcal{O}(\log M)$ per row.
• Total Time Complexity: $\mathcal{O}(\log(\text{Max} - \text{Min}) \times N \log M)$, which is extremely fast and well within competitive programming limits.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space since no extra data structures or flattened arrays are maintained.

9. Summary and Key Takeaways

• Odd Matrix Dimension Principle: Multiplying two odd integers ($N \times M$) always results in an odd total number of elements, ensuring a unique exact middle median index.
• Exploiting Sorted Rows: Because individual rows are already sorted, we avoid full sorting by utilizing Binary Search on the Answer Space combined with Upper Bound.
• Search Space Bounds: The answer lies between the minimum and maximum possible values present in the matrix (typically bounded between $1$ and $10^9$).
• Frequency Checking: The helper function counts how many matrix elements are $\le \text{mid}$ by summing the upper bound index results across each row.
• Binary Search Direction:
  • If $\text{count} \le \text{required}$, our candidate mid is too small; shift low = mid + 1.
  • If $\text{count} > \text{required}$, our candidate is valid but we can search for a smaller valid value; shift high = mid - 1.
• Optimal Efficiency: This reduces time complexity from $\mathcal{O}((N \cdot M) \log(N \cdot M))$ down to $\mathcal{O}(\log(\text{Range}) \cdot N \log M)$ with $\mathcal{O}(1)$ constant space.