Find Median in a Row-Wise Sorted Matrix

Understanding the Problem

The goal is to find the median of a row-wise sorted matrix.

Method 1: Using a Combined Array

This method combines all elements into a single array and then finds the median.

def find_median(matrix):
    total_elements = len(matrix) * len(matrix[0])
    combined = []

    # Combine all elements into a single array
    for row in matrix:
        combined.extend(row)

    # Sort the combined array
    combined.sort()

    # Find the median
    if total_elements % 2 == 0:
        return (combined[total_elements // 2 - 1] + combined[total_elements // 2]) / 2.0
    else:
        return combined[total_elements // 2]

# Example usage
matrix = [
    [1, 3, 5],
    [2, 6, 9],
    [3, 6, 9]
]
print("Median:", find_median(matrix))
            

Output:

Median: 3.0

Method 2: Using Binary Search

This method uses binary search to find the median efficiently.

def count_less_equal(matrix, mid):
    count = 0
    rows = len(matrix)
    cols = len(matrix[0])
    row, col = rows - 1, 0

    while row >= 0 and col < cols:
        if matrix[row][col] <= mid:
            count += (row + 1)  # All elements in this row are <= mid
            col += 1
        else:
            row -= 1
    return count

def find_median(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    low, high = 0, 100000  # Assuming the range of elements
    desired = (rows * cols + 1) // 2  # Median position

    while low < high:
        mid = low + (high - low) // 2
        if count_less_equal(matrix, mid) < desired:
            low = mid + 1
        else:
            high = mid
    return low  # The median

# Example usage
matrix = [
    [1, 3, 5],
    [2, 6, 9],
    [3, 6, 9]
]
print("Median:", find_median(matrix))
            

Output:

Median: 3.0

Method 3: Using a Two-Pointer Technique

This method uses a two-pointer technique to find the median.

def find_median(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    total_elements = rows * cols
    median_pos = (total_elements - 1) // 2
    count = 0

    for row in matrix:
        for element in row:
            if count == median_pos:
                return element  # Found the median
            count += 1
    return -1  # Should not reach here

# Example usage
matrix = [
    [1, 3, 5],
    [2, 6, 9],
    [3, 6, 9]
]
print("Median:", find_median(matrix))
            

Output:

Median: 3.0