Find Median of K Sorted Arrays

🎯

Find Median of K Sorted Arrays

hardHEAPAmazonGoogle

Imagine you have multiple sorted data streams from different sensors and want to find the median value across all sensors efficiently without merging all data explicitly.

💡 This problem involves combining multiple sorted arrays and finding a median without fully merging them. Beginners often struggle because merging all arrays naively is inefficient, and understanding how to use binary search on the answer space or heaps requires a shift from straightforward merging to more advanced techniques.

📋

Problem Statement

Given K sorted arrays of integers, find the median of all the elements combined. The median is the middle element if the total number of elements is odd, or the average of the two middle elements if even. Input: An array of K sorted integer arrays. Output: The median value as a float if needed.

1 ≤ K ≤ 10^4Total number of elements across all arrays ≤ 10^6Each array is sorted in non-decreasing orderElements can be negative or positive integers

💡

Example

Input"[[1,3,5],[2,4,6],[7,8,9]]"

Output5

Combined sorted array is [1,2,3,4,5,6,7,8,9], median is 5 (middle element).

Input"[[1,2],[3,4]]"

Output2.5

Combined sorted array is [1,2,3,4], median is (2+3)/2 = 2.5.

• All arrays empty → median undefined or error
• One array empty, others non-empty → median from non-empty arrays
• Arrays with duplicate elements → median accounts for duplicates
• Arrays of varying lengths including single-element arrays → median computed correctly

⚠️

Common Mistakes

Not handling empty arrays correctly

Code crashes or returns wrong median

✅ Check for empty arrays before accessing elements

Off-by-one errors in median index calculation

Returns wrong median value

✅ Carefully compute median indices as (total_len-1)//2 and total_len//2

Using linear search instead of binary search for counting elements ≤ mid

Algorithm becomes too slow for large inputs

✅ Use binary search (bisect or upper_bound) on each array

Not updating heap correctly when pushing next elements

Heap contains stale elements or misses elements, wrong median

✅ Always push next element from same array after popping

Assuming all arrays have same length

Index out of bounds or incorrect median

✅ Handle arrays of varying lengths carefully

🧠

Brute Force (Merge All Arrays Fully)

💡 This approach exists to build intuition by directly merging all arrays into one sorted array and then finding the median. It is simple but inefficient for large inputs, highlighting the need for better methods.

Intuition

Combine all arrays into one big sorted array by merging them fully, then pick the median element(s) from the merged array.

Algorithm

1. Initialize an empty list to hold all elements.
2. Iterate over each array and append all elements to the list.
3. Sort the combined list.
4. Return the median element(s) based on the total length.

💡 The main difficulty is realizing that merging all arrays fully is straightforward but costly, and sorting the combined list is the bottleneck.

</>

Code

def find_median_k_sorted_arrays(arrays):
    combined = []
    for arr in arrays:
        combined.extend(arr)
    combined.sort()
    n = len(combined)
    if n == 0:
        raise ValueError('No elements to find median')
    mid = n // 2
    if n % 2 == 1:
        return combined[mid]
    else:
        return (combined[mid - 1] + combined[mid]) / 2

# Driver code
if __name__ == '__main__':
    arrays = [[1,3,5],[2,4,6],[7,8,9]]
    print(find_median_k_sorted_arrays(arrays))  # Output: 5

Line Notes

combined = []Initialize a list to hold all elements from all arrays

for arr in arrays:Iterate over each sorted array to collect elements

combined.extend(arr)Add all elements from current array to combined list

combined.sort()Sort the combined list to get a fully sorted array

n = len(combined)Calculate total number of elements

if n == 0:Handle edge case where no elements exist

mid = n // 2Find middle index for median calculation

if n % 2 == 1:If odd number of elements, median is middle element

return combined[mid]Return the median element for odd length

else:If even number of elements, median is average of two middle elements

return (combined[mid - 1] + combined[mid]) / 2Calculate and return median for even length

import java.util.*;
public class MedianKSortedArrays {
    public static double findMedian(List<List<Integer>> arrays) {
        List<Integer> combined = new ArrayList<>();
        for (List<Integer> arr : arrays) {
            combined.addAll(arr);
        }
        Collections.sort(combined);
        int n = combined.size();
        if (n == 0) throw new IllegalArgumentException("No elements to find median");
        int mid = n / 2;
        if (n % 2 == 1) {
            return combined.get(mid);
        } else {
            return (combined.get(mid - 1) + combined.get(mid)) / 2.0;
        }
    }
    public static void main(String[] args) {
        List<List<Integer>> arrays = Arrays.asList(
            Arrays.asList(1,3,5),
            Arrays.asList(2,4,6),
            Arrays.asList(7,8,9)
        );
        System.out.println(findMedian(arrays)); // Output: 5
    }
}

Line Notes

List<Integer> combined = new ArrayList<>();Create a list to hold all elements from all arrays

for (List<Integer> arr : arrays)Iterate over each sorted array

combined.addAll(arr);Add all elements from current array to combined list

Collections.sort(combined);Sort the combined list to get a fully sorted array

int n = combined.size();Calculate total number of elements

if (n == 0) throw new IllegalArgumentExceptionHandle empty input edge case

int mid = n / 2;Find middle index for median calculation

if (n % 2 == 1)Check if number of elements is odd

return combined.get(mid);Return median element for odd length

elseHandle even number of elements

return (combined.get(mid - 1) + combined.get(mid)) / 2.0;Calculate median for even length

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
using namespace std;
double findMedianKSortedArrays(const vector<vector<int>>& arrays) {
    vector<int> combined;
    for (const auto& arr : arrays) {
        combined.insert(combined.end(), arr.begin(), arr.end());
    }
    sort(combined.begin(), combined.end());
    int n = combined.size();
    if (n == 0) throw invalid_argument("No elements to find median");
    int mid = n / 2;
    if (n % 2 == 1) {
        return combined[mid];
    } else {
        return (combined[mid - 1] + combined[mid]) / 2.0;
    }
}
int main() {
    vector<vector<int>> arrays = {{1,3,5},{2,4,6},{7,8,9}};
    cout << findMedianKSortedArrays(arrays) << endl; // Output: 5
    return 0;
}

Line Notes

vector<int> combined;Create a vector to hold all elements from all arrays

for (const auto& arr : arrays)Iterate over each sorted array

combined.insert(combined.end(), arr.begin(), arr.end());Append all elements from current array

sort(combined.begin(), combined.end());Sort the combined vector fully

int n = combined.size();Calculate total number of elements

if (n == 0) throw invalid_argumentHandle empty input edge case

int mid = n / 2;Find middle index for median calculation

if (n % 2 == 1)Check if number of elements is odd

return combined[mid];Return median element for odd length

elseHandle even number of elements

return (combined[mid - 1] + combined[mid]) / 2.0;Calculate median for even length

function findMedianKSortedArrays(arrays) {
    let combined = [];
    for (const arr of arrays) {
        combined = combined.concat(arr);
    }
    combined.sort((a,b) => a - b);
    const n = combined.length;
    if (n === 0) throw new Error('No elements to find median');
    const mid = Math.floor(n / 2);
    if (n % 2 === 1) {
        return combined[mid];
    } else {
        return (combined[mid - 1] + combined[mid]) / 2;
    }
}
// Driver code
const arrays = [[1,3,5],[2,4,6],[7,8,9]];
console.log(findMedianKSortedArrays(arrays)); // Output: 5

Line Notes

let combined = [];Initialize an array to hold all elements

for (const arr of arrays)Iterate over each sorted array

combined = combined.concat(arr);Concatenate current array elements

combined.sort((a,b) => a - b);Sort combined array numerically

const n = combined.length;Calculate total number of elements

if (n === 0) throw new ErrorHandle empty input edge case

const mid = Math.floor(n / 2);Find middle index for median calculation

if (n % 2 === 1)Check if number of elements is odd

return combined[mid];Return median element for odd length

elseHandle even number of elements

return (combined[mid - 1] + combined[mid]) / 2;Calculate median for even length

⏱

Complexity

TimeO(N log N) where N is total number of elements

SpaceO(N) to store all elements combined

We combine all elements into one list and sort it, which takes O(N log N) time. Space is O(N) for the combined list.

💡 For example, if total elements are 1,000,000, sorting takes roughly 20 million operations, which is slow for interviews.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large inputs but is useful to demonstrate understanding before optimizing.

🧠

Better Approach: Min-Heap K-way Merge

💡 This approach improves efficiency by merging arrays using a min-heap, avoiding full sorting. It is a classic technique for merging K sorted arrays and helps find the median by extracting elements in sorted order until the median position.

Intuition

Use a min-heap to always extract the smallest current element among the arrays, simulating a merge process without sorting all elements at once.

Algorithm

1. Calculate total number of elements across all arrays.
2. Initialize a min-heap and push the first element of each non-empty array along with array and element indices.
3. Pop elements from the heap one by one, pushing the next element from the same array when available.
4. Stop when the median position(s) is reached and compute the median.

💡 The challenge is managing indices and heap operations correctly to simulate the merge without full sorting.

</>

Code

import heapq

def find_median_k_sorted_arrays(arrays):
    min_heap = []
    total_len = sum(len(arr) for arr in arrays)
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(min_heap, (arr[0], i, 0))
    if total_len == 0:
        raise ValueError('No elements to find median')
    mid1 = (total_len - 1) // 2
    mid2 = total_len // 2
    count = -1
    median1 = median2 = None
    while min_heap:
        val, arr_idx, ele_idx = heapq.heappop(min_heap)
        count += 1
        if count == mid1:
            median1 = val
        if count == mid2:
            median2 = val
            break
        if ele_idx + 1 < len(arrays[arr_idx]):
            next_val = arrays[arr_idx][ele_idx + 1]
            heapq.heappush(min_heap, (next_val, arr_idx, ele_idx + 1))
    if total_len % 2 == 1:
        return float(median2)
    else:
        return (median1 + median2) / 2

# Driver code
if __name__ == '__main__':
    arrays = [[1,3,5],[2,4,6],[7,8,9]]
    print(find_median_k_sorted_arrays(arrays))  # Output: 5.0

Line Notes

min_heap = []Initialize min-heap to store current smallest elements

total_len = sum(len(arr) for arr in arrays)Calculate total number of elements across all arrays

for i, arr in enumerate(arrays):Iterate over each array with index

if arr:Only push if array is non-empty

heapq.heappush(min_heap, (arr[0], i, 0))Push first element with array and element indices

mid1 = (total_len - 1) // 2Calculate first median index (for even length)

mid2 = total_len // 2Calculate second median index

while min_heap:Extract elements from heap until median found

val, arr_idx, ele_idx = heapq.heappop(min_heap)Pop smallest element and track its origin

count += 1Count how many elements popped so far

if count == mid1: median1 = valRecord first median candidate

if count == mid2: median2 = val; breakRecord second median candidate and stop

if ele_idx + 1 < len(arrays[arr_idx]):If next element exists in same array, push it

heapq.heappush(min_heap, (next_val, arr_idx, ele_idx + 1))Push next element from same array

import java.util.*;
public class MedianKSortedArrays {
    static class Element implements Comparable<Element> {
        int val, arrIdx, eleIdx;
        Element(int v, int a, int e) { val = v; arrIdx = a; eleIdx = e; }
        public int compareTo(Element other) { return Integer.compare(this.val, other.val); }
    }
    public static double findMedian(List<List<Integer>> arrays) {
        PriorityQueue<Element> minHeap = new PriorityQueue<>();
        int totalLen = 0;
        for (List<Integer> arr : arrays) {
            totalLen += arr.size();
        }
        for (int i = 0; i < arrays.size(); i++) {
            List<Integer> arr = arrays.get(i);
            if (!arr.isEmpty()) {
                minHeap.offer(new Element(arr.get(0), i, 0));
            }
        }
        if (totalLen == 0) throw new IllegalArgumentException("No elements to find median");
        int mid1 = (totalLen - 1) / 2;
        int mid2 = totalLen / 2;
        int count = -1;
        int median1 = 0, median2 = 0;
        while (!minHeap.isEmpty()) {
            Element e = minHeap.poll();
            count++;
            if (count == mid1) median1 = e.val;
            if (count == mid2) {
                median2 = e.val;
                break;
            }
            List<Integer> arr = arrays.get(e.arrIdx);
            if (e.eleIdx + 1 < arr.size()) {
                minHeap.offer(new Element(arr.get(e.eleIdx + 1), e.arrIdx, e.eleIdx + 1));
            }
        }
        if (totalLen % 2 == 1) return (double) median2;
        else return (median1 + median2) / 2.0;
    }
    public static void main(String[] args) {
        List<List<Integer>> arrays = Arrays.asList(
            Arrays.asList(1,3,5),
            Arrays.asList(2,4,6),
            Arrays.asList(7,8,9)
        );
        System.out.println(findMedian(arrays)); // Output: 5.0
    }
}

Line Notes

static class Element implements Comparable<Element>Define a class to store value and indices for heap ordering

int totalLen = 0;Initialize total length counter

for (List<Integer> arr : arrays)Sum lengths of all arrays

for (int i = 0; i < arrays.size(); i++)Iterate over each array to push first elements

if (!arr.isEmpty())Only add if array is non-empty

minHeap.offer(new Element(arr.get(0), i, 0));Add first element of each array to heap

int mid1 = (totalLen - 1) / 2;Calculate first median index

int mid2 = totalLen / 2;Calculate second median index

while (!minHeap.isEmpty())Extract elements until median found

Element e = minHeap.poll();Pop smallest element

count++;Count elements popped

if (count == mid1) median1 = e.val;Record first median candidate

if (count == mid2)Record second median candidate and break

if (e.eleIdx + 1 < arr.size())If next element exists, add to heap

minHeap.offer(new Element(arr.get(e.eleIdx + 1), e.arrIdx, e.eleIdx + 1));Push next element from same array

#include <iostream>
#include <vector>
#include <queue>
#include <stdexcept>
using namespace std;
struct Element {
    int val, arrIdx, eleIdx;
    bool operator>(const Element& other) const {
        return val > other.val;
    }
};
double findMedianKSortedArrays(const vector<vector<int>>& arrays) {
    priority_queue<Element, vector<Element>, greater<Element>> minHeap;
    int totalLen = 0;
    for (const auto& arr : arrays) {
        totalLen += arr.size();
    }
    for (int i = 0; i < arrays.size(); i++) {
        if (!arrays[i].empty()) {
            minHeap.push({arrays[i][0], i, 0});
        }
    }
    if (totalLen == 0) throw invalid_argument("No elements to find median");
    int mid1 = (totalLen - 1) / 2;
    int mid2 = totalLen / 2;
    int count = -1;
    int median1 = 0, median2 = 0;
    while (!minHeap.empty()) {
        Element e = minHeap.top(); minHeap.pop();
        count++;
        if (count == mid1) median1 = e.val;
        if (count == mid2) {
            median2 = e.val;
            break;
        }
        if (e.eleIdx + 1 < arrays[e.arrIdx].size()) {
            minHeap.push({arrays[e.arrIdx][e.eleIdx + 1], e.arrIdx, e.eleIdx + 1});
        }
    }
    if (totalLen % 2 == 1) return (double)median2;
    else return (median1 + median2) / 2.0;
}
int main() {
    vector<vector<int>> arrays = {{1,3,5},{2,4,6},{7,8,9}};
    cout << findMedianKSortedArrays(arrays) << endl; // Output: 5.0
    return 0;
}

Line Notes

struct ElementStruct to hold value and indices for heap ordering

int totalLen = 0;Initialize total length counter

for (const auto& arr : arrays)Sum lengths of all arrays

for (int i = 0; i < arrays.size(); i++)Iterate over each array to push first elements

if (!arrays[i].empty())Only add if array is non-empty

minHeap.push({arrays[i][0], i, 0});Push first element of each array

int mid1 = (totalLen - 1) / 2;Calculate first median index

int mid2 = totalLen / 2;Calculate second median index

while (!minHeap.empty())Extract elements until median found

Element e = minHeap.top(); minHeap.pop();Pop smallest element

count++;Count elements popped

if (count == mid1) median1 = e.val;Record first median candidate

if (count == mid2)Record second median candidate and break

if (e.eleIdx + 1 < arrays[e.arrIdx].size())If next element exists, push it

minHeap.push({arrays[e.arrIdx][e.eleIdx + 1], e.arrIdx, e.eleIdx + 1});Push next element from same array

class Element {
    constructor(val, arrIdx, eleIdx) {
        this.val = val;
        this.arrIdx = arrIdx;
        this.eleIdx = eleIdx;
    }
}
function findMedianKSortedArrays(arrays) {
    const minHeap = [];
    function heapPush(e) {
        minHeap.push(e);
        let i = minHeap.length - 1;
        while (i > 0) {
            let p = Math.floor((i - 1) / 2);
            if (minHeap[p].val <= minHeap[i].val) break;
            [minHeap[p], minHeap[i]] = [minHeap[i], minHeap[p]];
            i = p;
        }
    }
    function heapPop() {
        const top = minHeap[0];
        const last = minHeap.pop();
        if (minHeap.length > 0) {
            minHeap[0] = last;
            let i = 0;
            while (true) {
                let left = 2 * i + 1, right = 2 * i + 2, smallest = i;
                if (left < minHeap.length && minHeap[left].val < minHeap[smallest].val) smallest = left;
                if (right < minHeap.length && minHeap[right].val < minHeap[smallest].val) smallest = right;
                if (smallest === i) break;
                [minHeap[i], minHeap[smallest]] = [minHeap[smallest], minHeap[i]];
                i = smallest;
            }
        }
        return top;
    }
    let totalLen = 0;
    for (let i = 0; i < arrays.length; i++) {
        totalLen += arrays[i].length;
    }
    for (let i = 0; i < arrays.length; i++) {
        if (arrays[i].length > 0) {
            heapPush(new Element(arrays[i][0], i, 0));
        }
    }
    if (totalLen === 0) throw new Error('No elements to find median');
    const mid1 = Math.floor((totalLen - 1) / 2);
    const mid2 = Math.floor(totalLen / 2);
    let count = -1;
    let median1 = 0, median2 = 0;
    while (minHeap.length > 0) {
        const e = heapPop();
        count++;
        if (count === mid1) median1 = e.val;
        if (count === mid2) {
            median2 = e.val;
            break;
        }
        if (e.eleIdx + 1 < arrays[e.arrIdx].length) {
            heapPush(new Element(arrays[e.arrIdx][e.eleIdx + 1], e.arrIdx, e.eleIdx + 1));
        }
    }
    if (totalLen % 2 === 1) return median2;
    else return (median1 + median2) / 2;
}
// Driver code
const arrays = [[1,3,5],[2,4,6],[7,8,9]];
console.log(findMedianKSortedArrays(arrays)); // Output: 5

Line Notes

class ElementClass to hold value and indices for heap ordering

let totalLen = 0;Initialize total length counter

for (let i = 0; i < arrays.length; i++)Iterate over each array to push first elements

if (arrays[i].length > 0)Only add if array is non-empty

heapPush(new Element(arrays[i][0], i, 0));Push first element of each array

const mid1 = Math.floor((totalLen - 1) / 2);Calculate first median index

const mid2 = Math.floor(totalLen / 2);Calculate second median index

while (minHeap.length > 0)Extract elements until median found

const e = heapPop();Pop smallest element

count++;Count elements popped

if (count === mid1) median1 = e.val;Record first median candidate

if (count === mid2)Record second median candidate and break

if (e.eleIdx + 1 < arrays[e.arrIdx].length)If next element exists, push it

heapPush(new Element(arrays[e.arrIdx][e.eleIdx + 1], e.arrIdx, e.eleIdx + 1));Push next element from same array

⏱

Complexity

TimeO(N log K) where N is total elements, K is number of arrays

SpaceO(K) for the heap

Each element is pushed and popped once from the heap of size K, so operations cost O(log K).

💡 For example, with 1,000,000 elements and 100 arrays, this is roughly 1,000,000 * log(100) ≈ 6,600,000 operations, much faster than brute force.

Interview Verdict: Accepted / Efficient for large inputs

This approach is practical and commonly accepted in interviews for this problem.

🧠

Optimal Approach: Binary Search on Value Range

💡 This approach uses binary search on the value range to find the median without merging or heap operations. It leverages the sorted arrays to count how many elements are less than or equal to a candidate median, narrowing down the median value efficiently.

Intuition

Instead of merging, guess a median value and count how many elements are less or equal to it across all arrays. Adjust guess based on count until the median is found.

Algorithm

1. Find the global minimum and maximum values across all arrays to define search range.
2. Perform binary search on this value range.
3. For each mid value, count how many elements across all arrays are ≤ mid using binary search.
4. Adjust search range based on count until the median position is found.
5. Return the median value or average of two median values depending on total length parity.

💡 The key difficulty is correctly counting elements ≤ mid efficiently and handling even/odd total length cases.

</>

Code

import bisect

def find_median_k_sorted_arrays(arrays):
    total_len = sum(len(arr) for arr in arrays)
    if total_len == 0:
        raise ValueError('No elements to find median')
    min_val = min((arr[0] for arr in arrays if arr), default=0)
    max_val = max((arr[-1] for arr in arrays if arr), default=0)
    def count_less_equal(x):
        count = 0
        for arr in arrays:
            count += bisect.bisect_right(arr, x)
        return count
    left, right = min_val, max_val
    mid1 = (total_len - 1) // 2
    mid2 = total_len // 2
    median1 = median2 = None
    while left <= right:
        mid = (left + right) // 2
        c = count_less_equal(mid)
        if c <= mid1:
            left = mid + 1
        else:
            right = mid - 1
    median1 = left
    left, right = min_val, max_val
    while left <= right:
        mid = (left + right) // 2
        c = count_less_equal(mid)
        if c <= mid2:
            left = mid + 1
        else:
            right = mid - 1
    median2 = left
    if total_len % 2 == 1:
        return float(median2)
    else:
        return (median1 + median2) / 2

# Driver code
if __name__ == '__main__':
    arrays = [[1,3,5],[2,4,6],[7,8,9]]
    print(find_median_k_sorted_arrays(arrays))  # Output: 5.0

Line Notes

total_len = sum(len(arr) for arr in arrays)Calculate total number of elements

min_val = min((arr[0] for arr in arrays if arr), default=0)Find global minimum value

max_val = max((arr[-1] for arr in arrays if arr), default=0)Find global maximum value

def count_less_equal(x):Helper to count elements ≤ x using binary search

count += bisect.bisect_right(arr, x)Count elements ≤ x in each array efficiently

while left <= right:Binary search loop to find median2

c = count_less_equal(mid)Count elements ≤ mid

if c <= mid1: left = mid + 1Adjust search range if count too small

else: right = mid - 1Adjust search range if count too large

median1 = leftStore first median candidate

left, right = min_val, max_valReset search range for second median

if c <= mid2: left = mid + 1Adjust search range if count too small

median2 = leftStore second median candidate

if total_len % 2 == 1: return float(median2)Return median for odd length

else: return (median1 + median2) / 2Return average for even length

import java.util.*;
public class MedianKSortedArrays {
    public static int countLessEqual(List<List<Integer>> arrays, int x) {
        int count = 0;
        for (List<Integer> arr : arrays) {
            int idx = Collections.binarySearch(arr, x);
            if (idx < 0) idx = -idx - 1;
            else {
                while (idx < arr.size() && arr.get(idx) == x) idx++;
            }
            count += idx;
        }
        return count;
    }
    public static double findMedian(List<List<Integer>> arrays) {
        int totalLen = 0;
        int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
        for (List<Integer> arr : arrays) {
            totalLen += arr.size();
            if (!arr.isEmpty()) {
                minVal = Math.min(minVal, arr.get(0));
                maxVal = Math.max(maxVal, arr.get(arr.size() - 1));
            }
        }
        if (totalLen == 0) throw new IllegalArgumentException("No elements to find median");
        int mid1 = (totalLen - 1) / 2;
        int mid2 = totalLen / 2;
        int left = minVal, right = maxVal;
        int median1 = 0, median2 = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int c = countLessEqual(arrays, mid);
            if (c <= mid1) left = mid + 1;
            else right = mid - 1;
        }
        median1 = left;
        left = minVal;
        right = maxVal;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int c = countLessEqual(arrays, mid);
            if (c <= mid2) left = mid + 1;
            else right = mid - 1;
        }
        median2 = left;
        if (totalLen % 2 == 1) return (double) median2;
        else return (median1 + median2) / 2.0;
    }
    public static void main(String[] args) {
        List<List<Integer>> arrays = Arrays.asList(
            Arrays.asList(1,3,5),
            Arrays.asList(2,4,6),
            Arrays.asList(7,8,9)
        );
        System.out.println(findMedian(arrays)); // Output: 5.0
    }
}

Line Notes

int count = 0;Initialize count of elements ≤ x

int idx = Collections.binarySearch(arr, x);Binary search to find insertion point or exact match

if (idx < 0) idx = -idx - 1;Convert negative insertion point to index

while (idx < arr.size() && arr.get(idx) == x) idx++;Move index to count duplicates equal to x

count += idx;Add count of elements ≤ x in current array

int totalLen = 0;Calculate total number of elements

minVal = Math.min(minVal, arr.get(0));Find global minimum value

maxVal = Math.max(maxVal, arr.get(arr.size() - 1));Find global maximum value

while (left <= right)Binary search loop to find median2

int c = countLessEqual(arrays, mid);Count elements ≤ mid

if (c <= mid1) left = mid + 1; else right = mid - 1;Adjust search range

median1 = left;Store first median candidate

left = minVal;Reset search range for second median

right = maxVal;Reset search range for second median

c = countLessEqual(arrays, mid);Count elements ≤ mid

if (c <= mid2) left = mid + 1; else right = mid - 1;Adjust search range

median2 = left;Store second median candidate

if (totalLen % 2 == 1) return (double) median2;Return median for odd length

else return (median1 + median2) / 2.0;Return average for even length

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
using namespace std;
int countLessEqual(const vector<vector<int>>& arrays, int x) {
    int count = 0;
    for (const auto& arr : arrays) {
        count += upper_bound(arr.begin(), arr.end(), x) - arr.begin();
    }
    return count;
}
double findMedianKSortedArrays(const vector<vector<int>>& arrays) {
    int totalLen = 0;
    int minVal = INT_MAX, maxVal = INT_MIN;
    for (const auto& arr : arrays) {
        totalLen += arr.size();
        if (!arr.empty()) {
            minVal = min(minVal, arr.front());
            maxVal = max(maxVal, arr.back());
        }
    }
    if (totalLen == 0) throw invalid_argument("No elements to find median");
    int mid1 = (totalLen - 1) / 2;
    int mid2 = totalLen / 2;
    int left = minVal, right = maxVal;
    int median1 = 0, median2 = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int c = countLessEqual(arrays, mid);
        if (c <= mid1) left = mid + 1;
        else right = mid - 1;
    }
    median1 = left;
    left = minVal;
    right = maxVal;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int c = countLessEqual(arrays, mid);
        if (c <= mid2) left = mid + 1;
        else right = mid - 1;
    }
    median2 = left;
    if (totalLen % 2 == 1) return (double)median2;
    else return (median1 + median2) / 2.0;
}
int main() {
    vector<vector<int>> arrays = {{1,3,5},{2,4,6},{7,8,9}};
    cout << findMedianKSortedArrays(arrays) << endl; // Output: 5.0
    return 0;
}

Line Notes

int count = 0;Initialize count of elements ≤ x

count += upper_bound(arr.begin(), arr.end(), x) - arr.begin();Count elements ≤ x using binary search

int totalLen = 0;Calculate total number of elements

minVal = min(minVal, arr.front());Find global minimum value

maxVal = max(maxVal, arr.back());Find global maximum value

while (left <= right)Binary search loop to find median2

int c = countLessEqual(arrays, mid);Count elements ≤ mid

if (c <= mid1) left = mid + 1; else right = mid - 1;Adjust search range

median1 = left;Store first median candidate

left = minVal;Reset search range for second median

right = maxVal;Reset search range for second median

c = countLessEqual(arrays, mid);Count elements ≤ mid

if (c <= mid2) left = mid + 1; else right = mid - 1;Adjust search range

median2 = left;Store second median candidate

if (totalLen % 2 == 1) return (double)median2;Return median for odd length

else return (median1 + median2) / 2.0;Return average for even length

function countLessEqual(arrays, x) {
    let count = 0;
    for (const arr of arrays) {
        let left = 0, right = arr.length;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (arr[mid] <= x) left = mid + 1;
            else right = mid;
        }
        count += left;
    }
    return count;
}
function findMedianKSortedArrays(arrays) {
    let totalLen = 0;
    let minVal = Infinity, maxVal = -Infinity;
    for (const arr of arrays) {
        totalLen += arr.length;
        if (arr.length > 0) {
            minVal = Math.min(minVal, arr[0]);
            maxVal = Math.max(maxVal, arr[arr.length - 1]);
        }
    }
    if (totalLen === 0) throw new Error('No elements to find median');
    const mid1 = Math.floor((totalLen - 1) / 2);
    const mid2 = Math.floor(totalLen / 2);
    let left = minVal, right = maxVal;
    let median1 = 0, median2 = 0;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let c = countLessEqual(arrays, mid);
        if (c <= mid1) left = mid + 1;
        else right = mid - 1;
    }
    median1 = left;
    left = minVal;
    right = maxVal;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let c = countLessEqual(arrays, mid);
        if (c <= mid2) left = mid + 1;
        else right = mid - 1;
    }
    median2 = left;
    if (totalLen % 2 === 1) return median2;
    else return (median1 + median2) / 2;
}
// Driver code
const arrays = [[1,3,5],[2,4,6],[7,8,9]];
console.log(findMedianKSortedArrays(arrays)); // Output: 5

Line Notes

function countLessEqual(arrays, x)Helper to count elements ≤ x using binary search

while (left < right)Binary search loop to find insertion point

if (arr[mid] <= x) left = mid + 1; else right = mid;Adjust search range based on comparison

count += left;Add count of elements ≤ x in current array

let totalLen = 0;Calculate total number of elements

minVal = Math.min(minVal, arr[0]);Find global minimum value

maxVal = Math.max(maxVal, arr[arr.length - 1]);Find global maximum value

while (left <= right)Binary search loop to find median2

let c = countLessEqual(arrays, mid);Count elements ≤ mid

if (c <= mid1) left = mid + 1; else right = mid - 1;Adjust search range

median1 = left;Store first median candidate

left = minVal;Reset search range for second median

right = maxVal;Reset search range for second median

c = countLessEqual(arrays, mid);Count elements ≤ mid

if (c <= mid2) left = mid + 1; else right = mid - 1;Adjust search range

median2 = left;Store second median candidate

if (totalLen % 2 === 1) return median2;Return median for odd length

else return (median1 + median2) / 2;Return average for even length

⏱

Complexity

TimeO(K log M log N) where K is number of arrays, M is value range, N is average array length

SpaceO(1) additional space

Binary search on value range takes log M steps, each counting elements in K arrays with binary search O(log N).

💡 For example, if value range is 10^9, arrays are 100, and average length 10,000, this is about 30 * 100 * 14 = 42,000 operations, very efficient.

Interview Verdict: Accepted / Most optimal for large inputs

This approach is the best for very large inputs and shows mastery of binary search on answer technique.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the heap-based k-way merge is usually best balance of clarity and efficiency. Binary search on value range is optimal but more complex to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(N log N)	O(N)	No	N/A	Mention only - never code for large inputs
2. Min-Heap K-way Merge	O(N log K)	O(K)	No	N/A	Code this approach for balance of clarity and efficiency
3. Binary Search on Value Range	O(K log M log N)	O(1)	No	N/A	Mention as optimal; code if confident

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying input/output, then explain brute force, improve to heap-based merging, and finally discuss binary search on value range. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and constraints, including empty arrays and duplicates.Step 2: Describe the brute force approach to merge all arrays and find median.Step 3: Explain the min-heap k-way merge to improve efficiency.Step 4: Introduce binary search on the value range as the optimal solution.Step 5: Code the chosen approach and test with edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 7min. Total ~25min

What the Interviewer Tests

The interviewer tests your understanding of merging sorted arrays, efficient median finding, handling edge cases, and ability to optimize from brute force to advanced techniques.

Common Follow-ups

• What if arrays are not sorted? → Need to sort or use different approach.
• How to find kth smallest element instead of median? → Similar heap or binary search approach.

💡 These follow-ups test your adaptability and understanding of related problems.

🔍

Pattern Recognition

When to Use

1) Multiple sorted arrays given, 2) Need median or kth element, 3) Merging all arrays fully is expensive, 4) Efficient counting or heap-based merging possible

Signature Phrases

Find median of k sorted arraysk-way mergecount elements less than or equal to mid

NOT This Pattern When

Sorting a single unsorted array or finding median in unsorted data

Similar Problems

Median of Two Sorted Arrays - similar median finding with two arraysKth Smallest Element in a Sorted Matrix - similar counting and binary searchMerge K Sorted Lists - similar heap-based merging

Practice

1. You have K identical machines and a list of jobs, each with a start time and duration. You want to assign each job to a machine so that each machine processes jobs sequentially without overlap, always choosing the earliest available machine with the smallest index. Which algorithmic approach guarantees an optimal assignment minimizing waiting times and correctly handles job scheduling in chronological order?

easy

A. Greedy approach that assigns each job to the first machine found free by scanning all machines linearly.

B. Use a min-heap to track available machines by their next free time and assign jobs in order of start time, updating machine availability accordingly.

C. Dynamic programming that tries all possible assignments and picks the minimum total completion time.

D. Sort jobs by duration and assign them to machines in that order to minimize total processing time.

Solution

1. Step 1: Understand the problem constraints

   The problem requires assigning jobs to machines so that each job starts no earlier than its start time, machines process jobs sequentially, and the earliest available machine with the smallest index is chosen.

2. Step 2: Identify the correct approach

   Using a min-heap to track machine availability by next free time allows efficient retrieval of the earliest available machine. Sorting jobs by start time ensures chronological processing. This approach guarantees optimal scheduling and respects machine indices.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Min-heap + sorting jobs by start time -> optimal scheduling [OK]

Hint: Min-heap tracks earliest available machine efficiently [OK]

Common Mistakes:

• Using linear search for machine availability leads to O(nK) time
• Sorting by duration ignores job start times and causes conflicts
• DP approach is infeasible due to large state space

2. You are given k sorted lists of integers. Your task is to find the smallest range that includes at least one number from each of the k lists. Which algorithmic approach guarantees an optimal solution with efficient time complexity?

easy

A. Use a min-heap to track the current minimum element among the heads of each list while maintaining the current maximum, updating the range as you iterate.

B. Apply a greedy approach by always picking the smallest element from any list and expanding the range until all lists are covered.

C. Sort all elements from all lists into one array and use a dynamic programming approach to find the minimal range covering all lists.

D. Use a brute force approach enumerating all combinations of elements from each list and selecting the minimal range.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding a range that covers at least one element from each of the k sorted lists, minimizing the range size.

2. Step 2: Identify the optimal approach

   Using a min-heap to track the smallest current element from each list and maintaining the maximum element seen so far allows efficient updates of the range while iterating through the lists.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap approach efficiently tracks min and max for optimal range [OK]

Hint: Min-heap tracks min and max for optimal range [OK]

Common Mistakes:

• Thinking brute force is feasible for large k
• Assuming greedy picking smallest element always works
• Confusing DP applicability here

3. Given the following Python code to find the nth ugly number, what is the output when nthUglyNumber(4) is called?

easy

A. 6

B. 5

C. 8

D. 4

Solution

1. Step 1: Trace heap pops and pushes for n=4

   Initial heap: [1]. Iteration 1 pops 1, pushes 2,3,5. Iteration 2 pops 2, pushes 4,6,10. Iteration 3 pops 3, pushes 6,9,15 (6 already in seen, skip). Iteration 4 pops 4, pushes 8,12,20.

2. Step 2: Identify the 4th popped ugly number

   The popped numbers in order are 1,2,3,4. The 4th ugly number popped is 4, so the output is 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   4 is the 4th ugly number [OK]

Hint: Trace heap pops carefully to find nth ugly number [OK]

Common Mistakes:

• Off-by-one error in loop iterations
• Confusing popped value with pushed values

4. What is the time complexity of the optimal min-heap based algorithm for finding the smallest range covering k sorted lists, where N is the total number of elements across all lists and k is the number of lists?

medium

A. O(N log k) because each of the N elements is pushed and popped from a heap of size k.

B. O(k log N) because the heap size grows with total elements N and operations depend on k.

C. O(N * k) because each element is processed k times in the heap operations.

D. O(N) because each element is processed exactly once without extra overhead.

Solution

1. Step 1: Analyze heap operations

   Heap size is at most k since it stores one element from each list at a time.

2. Step 2: Count total operations

   Each of the N elements is pushed and popped exactly once, each heap operation costs O(log k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap size k leads to O(log k) per operation, total N elements processed [OK]

Hint: Heap size k means log k per operation, total N elements [OK]

Common Mistakes:

• Assuming heap size grows with N, confusing log N vs log k
• Multiplying N by k incorrectly
• Ignoring heap operation cost

5. Consider the following buggy code for finding the nth ugly number. Which line contains the subtle bug that causes incorrect results or performance issues?

medium

A. Line 3: heap initialization with [1]

B. Line 4: Missing initialization of the 'seen' set

C. Line 7: Loop runs n times popping from heap

D. Line 10: Multiplying ugly by factors 2, 3, and 5

Solution

1. Step 1: Identify missing duplicate check

   The 'seen' set is not initialized and the check to avoid pushing duplicates is missing, causing duplicates to be pushed repeatedly.

2. Step 2: Understand impact of missing 'seen'

   Without 'seen', the heap grows unnecessarily large with duplicates, causing performance degradation and possibly incorrect nth number due to repeated values.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing 'seen' set causes duplicates and performance issues [OK]

Hint: Always track seen elements to avoid duplicates in heap [OK]

Common Mistakes:

• Forgetting to initialize or use 'seen'
• Assuming heap automatically avoids duplicates