How to find median of m sorted arrays?

Question

How to find the median of M sorted arrays of integers? Where the size of each array is bounded by N. Assume that each array contains sorted integer elements.

There are two variation of this question.

Each array has same size.
Each array has different size.

So you're looking for the single median of the concatenation of the `m` sorted arrays? What have you tried so far? — Teepeemm, Aug 31 '14 at 23:48
@teepeemm I am sorry for poor phrasing. I have updated the questions. I tried extending the algorithm of median of two sorted array of different size. But couldn't reach to a particular complexity. — rgaut, Sep 01 '14 at 17:18
@alfasin There are M sorted arrays each array contains integer elements. Hope this is clear now. — rgaut, Sep 01 '14 at 17:21
@beaker: See my comment in the answer given by Shankhoneer below. — rgaut, Sep 01 '14 at 18:31
possible duplicate of [Median of 5 sorted arrays](http://stackoverflow.com/questions/6182488/median-of-5-sorted-arrays) — Hesham Attia, Dec 25 '14 at 11:11

score 0 · Answer 1 · answered Sep 01 '14 at 00:08

0

I will just give an hint since you didnt mention what you have tried:

1. Create a min heap (MIN-HEAPIFY) using all the 0-th element of the m arrays
2. Extract min and add an element into the heap from the array from which the min was extracted
3. Assuming all m arrays are of n length EXTRACT-MIN from heap till you get m*n/2 elements.

Try to prove how this solution works and come up with a code.

answered Sep 01 '14 at 00:08

Shankhoneer Chakrovarty

690
1
6
19

I thought the same answer but the complexity in such case is Creating Heap O(M) + extracting MN/2 elements from heap will cause MNlogM complexity, so overall complexity will be O(MNlogM) I am looking for something better. – rgaut Sep 01 '14 at 17:21
Extracting one min element from heap will be O(lgM) so extracting n/2 element will be O(NlgM). Reference: Introduction To algorithms By Cormen et al. Heapsort Chapter, HEAP-EXTRACT-MAX algorithm – Shankhoneer Chakrovarty Sep 03 '14 at 01:26
Hmmm How many elements you are extracting from heap ??? MN/2 right? You need to call extract-MIN MN times and each call will cost logM so total it will be MNlogM. – rgaut Sep 03 '14 at 21:43
Yes you are correct I mistook N for the whole input size whereas N is actually size of one array. If you want an algorithm better than this then you have to do binary search. I will update the post with the code and approach later tonight. – Shankhoneer Chakrovarty Sep 04 '14 at 00:03
@ShankhoneerChakrovarty where is your answer? – Pythoner May 02 '18 at 01:14
@Pythoner The question is a duplicate of [Median of 5 sorted arrays](https://stackoverflow.com/questions/6182488/median-of-5-sorted-arrays) so I didnt bother to post the answer here. The top answer in that question solves the problem completely taking care of all the edge cases. – Shankhoneer Chakrovarty May 09 '18 at 08:52
Time Limit Exceeded. – Charlie 木匠 Nov 27 '18 at 18:57

score 0 · Answer 2 · answered May 02 '18 at 01:15

A java version

public class Solution {
    /**
     * @param nums: the given k sorted arrays
     * @return: the median of the given k sorted arrays
     */
    public double findMedian(int[][] nums) {
        int n = getTotal(nums);
        if (n == 0) {
            return 0;
        }

        if (n % 2 != 0) {
            return findKth(nums, n / 2 + 1);
        }

        return (findKth(nums, n / 2) + findKth(nums, n / 2 + 1)) / 2.0;
    }

    private int getTotal(int[][] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i].length;
        }
        return sum;
    }

    // k is not zero-based, it starts from 1.
    private int findKth(int[][] nums, int k) {
        int start = 0, end = Integer.MAX_VALUE;

        // find the last number x that >= k numbers are >= x. 
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (getGTE(nums, mid) >= k) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (getGTE(nums, start) >= k) {
            return start;
        }

        return end;
    }

    // get how many numbers greater than or equal to val in 2d array
    private int getGTE(int[][] nums, int val) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += getGTE(nums[i], val);
        }
        return sum;
    }

    // get how many numbers greater than or equal to val in an array
    private int getGTE(int[] nums, int val) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int start = 0, end = nums.length - 1;

        // find first element >= val 
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] >= val) {
                end = mid;
            } else {
                start = mid;
            }
        }

        if (nums[start] >= val) {
            return nums.length - start;
        }

        if (nums[end] >= val) {
            return nums.length - end;
        }

        return 0;
    }
    }

How to find median of m sorted arrays?

2 Answers2