We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Median of a Row Wise Sorted Matrix

Number: 2522

Difficulty: Medium

Paid? Yes

Companies: DE Shaw

Problem Description

Given an m x n matrix where every row is sorted in non-decreasing order and the total number of elements is odd, return the median of the matrix. The challenge is to accomplish this in less than O(m * n) time complexity.

Key Insights

  • Each row of the matrix is individually sorted, allowing efficient binary search operations.
  • Instead of merging rows or flattening the matrix, we can perform binary search on the value range (from the minimum element to the maximum element in the matrix).
  • For every candidate value during the binary search over the answer range, we can count how many elements in the matrix are less than or equal to it using binary search on each row.
  • The median is the smallest number for which the count of elements less than or equal to it is at least (m * n // 2 + 1).

Space and Time Complexity

Time Complexity: O(m * log(n) * log(max - min)) Space Complexity: O(1)

Solution

We use a binary search on the value range of the matrix. First, determine the minimum (from the first element of each row) and maximum (from the last element of each row) values. Then use binary search as follows:

  1. Calculate mid = (low + high) / 2.
  2. For each row, count the number of elements no greater than mid using binary search.
  3. Sum these counts across all rows.
  4. If the total count is less than (m*n//2 + 1), adjust the low pointer to mid + 1; otherwise, adjust the high pointer to mid - 1.
  5. Continue until low exceeds high. The current low will be the median. The main trick is to perform binary search twice: once on the value range and once on each row, keeping the overall time complexity efficient.

Code Solutions

def count_less_or_equal(row, target):
    # Binary search in a row to find the count of elements <= target.
    lo, hi = 0, len(row)
    while lo < hi:
        mid = (lo + hi) // 2
        if row[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def find_matrix_median(grid):
    m, n = len(grid), len(grid[0])
    # Get the minimum and maximum possible values in the matrix.
    low = min(row[0] for row in grid)
    high = max(row[-1] for row in grid)
    desired = (m * n) // 2 + 1

    while low <= high:
        mid_val = (low + high) // 2
        count = 0
        # Count elements less than or equal to mid_val in each row.
        for row in grid:
            count += count_less_or_equal(row, mid_val)
        if count < desired:
            low = mid_val + 1
        else:
            high = mid_val - 1
    return low

# Example usage:
grid = [[1,1,2], [2,3,3], [1,3,4]]
print(find_matrix_median(grid))  # Expected output: 2
← Back to All Questions