Find median in a row wise sorted matrix

Problem Statement

Given a row-wise sorted matrix of size m x n where m and n are always odd, find the median of the matrix.

Example:

• Input: matrix = [[1, 3, 5], [2, 6, 9], [3, 6, 9]]
• Output: 5
• Explanation: If we flatten and sort: [1, 2, 3, 3, 5, 6, 6, 9, 9]. Median is the 5th element = 5

Approach 1: Brute Force (Flatten and Sort)

Intuition

Flatten the matrix into a 1D array, sort it, and return the middle element.

Algorithm

1. Copy all elements into a 1D array
2. Sort the array
3. Return the element at index (m*n)/2

import java.util.*;

public class Solution {
    public int findMedianBrute(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] arr = new int[m * n];
        int index = 0;
        
        // Flatten the matrix
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr[index++] = matrix[i][j];
            }
        }
        
        // Sort and return median
        Arrays.sort(arr);
        return arr[(m * n) / 2];
    }
}

Complexity Analysis

• Time Complexity: O(mnlog(m*n)) - Sorting all elements
• Space Complexity: O(m*n) - Storing all elements in array

Approach 2: Binary Search on Value Range (Optimal)

Intuition

The median has a special property: exactly (m*n)/2 elements are smaller than or equal to it. We can binary search on the value range [min, max] and count elements less than or equal to mid.

Since each row is sorted, we can efficiently count elements ≤ mid using binary search (upper_bound) in each row.

Algorithm

1. Find the minimum (first column min) and maximum (last column max) in matrix
2. Binary search on this range:
   • For mid value, count elements ≤ mid across all rows
   • If count ≤ (m*n)/2, search in right half
   • Else search in left half
3. Return the answer when low == high

import java.util.*;

public class Solution {
    private int countLessOrEqual(int[][] matrix, int target) {
        int count = 0;
        for (int[] row : matrix) {
            // Binary search to count elements <= target
            count += upperBound(row, target);
        }
        return count;
    }
    
    private int upperBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    public int findMedian(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        
        // Find min and max in matrix
        int low = Integer.MAX_VALUE, high = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            low = Math.min(low, matrix[i][0]);
            high = Math.max(high, matrix[i][n - 1]);
        }
        
        int desired = (m * n + 1) / 2;  // Position of median
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            int count = countLessOrEqual(matrix, mid);
            
            if (count < desired) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        
        return low;
    }
}

Complexity Analysis

• Time Complexity: O(m * log(max-min) * log(n))
  • Binary search on value range: O(log(max-min))
  • For each mid, counting in m rows: O(m * log(n))
• Space Complexity: O(1) - Only using constant extra space

Approach 3: Using Min-Heap (Merge K Sorted Lists Approach)

Intuition

Use a min-heap to merge k sorted rows and extract elements until we reach the median position.

Complexity Analysis

• Time Complexity: O((m*n/2) * log(m)) - Extract median position elements
• Space Complexity: O(m) - Heap stores at most m elements

Key Takeaways

1. Binary search on answer is a powerful technique when direct computation is complex
2. The key insight: median has exactly (n*m)/2 elements less than or equal to it
3. Upper bound in each row efficiently counts elements ≤ target
4. This technique works even when elements can repeat
5. The heap approach is good but suboptimal compared to binary search
6. Similar pattern applies to finding kth smallest element in sorted matrix