package com.freetymekiyan.algorithms.other;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Given n sorted arrays, find the median of them.
 * <p>
 * Companies: Facebook
 */
public class MedianOfNSortedArrays {

    /**
     * Recall median of 2 sorted arrays. Binary search. O(logn).
     * Cannot use binary search anymore here.
     * <p>
     * Assuming the arrays are sorted strictly ascending.
     * <p>
     * We may put all the first numbers of an array to a min heap.
     * This min heap will return the next minimum value.
     * And maintain an array of n pointers, each points to one array.
     * Need to know which array this value belongs to.
     * Increment the index of that array.
     * If the pointer is out of bounds, then no more numbers of that array will be added to heap.
     * <p>
     * A linear scan to find out which array the minimum value belongs to is expansive.
     * Can we return which array and the index together with the minimum value?
     * Sounds like another array.
     */
    public double getMedian(int[][] arrs) {
        if (arrs.length == 0) return 0;
        // int[] is {row, column, value}
        PriorityQueue<int[]> pq = new PriorityQueue<>(arrs.length, Comparator.comparingInt(a -> a[2]));
        int n = 0; // Total number of integers.
        for (int i = 0; i < arrs.length; i++) {
            pq.offer(new int[]{i, 0, arrs[i][0]});
            n += arrs[i].length;
        }

        /*
         * Note that median's definition is:
         * If total number is odd, median is the number right in the middle.
         * If total number is even, median is the average of the 2 numbers in the middle.
         */
        double median = 0;
        /*
         * When n = 2k+1, n/2 = k, loop runs k times. The next number is the median.
         * E.g. n = 7, n/2 = 3, the 4th number is the median.
         * When n = 2k, n/2 = k, loop runs k times.
         * E.g. n = 8, n/2 = 4, the average of 4th and 5th is the median.
         */
        for (int i = 0; i < n / 2; i++) {
            int[] min = pq.poll();
            if (min[1] < arrs[min[0]].length - 1) {
                min[1]++; // Move pointer one step back.
                min[2] = arrs[min[0]][min[1]]; // Update value.
                pq.offer(min); // Add to heap.
            }
            if (i == n / 2 - 2 && n % 2 == 0) { // When n is even, record the last 2 values.
                median = min[2];
            } else if (i == n / 2 - 1 && n % 2 == 0) {
                median = (median + min[2]) / 2;
            } else if (i == n / 2 - 1 && n % 2 == 1) { // When n is odd, poll one more value at the last iteration.
                median = pq.poll()[2];
            }
        }
        return median;
    }
}
@@ -246,291 +246,163 @@
   * 
-Recall median of 2 sorted arrays. Binary search. O(logn).%0A     * Cannot use binary search anymore here.%0A     * %3Cp%3E%0A     * Assuming the arrays are sorted strictly ascending.%0A     * %3Cp%3E%0A     * We may put all the first numbers of an array to
+Heap. Merge.%0A     * Just like how we merge 2 sorted arrays, we can do the same to N arrays.%0A     * The only difference is that
  a min
- 
+-
 heap
-.%0A     * This min heap will return
+ is needed to find
  the
@@ -414,22 +414,16 @@
  minimum
- value
 .%0A     *
@@ -427,1506 +427,930 @@
   * 
-And maintain an array of n pointers, each points to one array.%0A     * Need to know which array this value belongs to.%0A     * Increment the index of that array.%0A     * If the pointer is out of bounds, then no more numbers of that array will be added to heap.%0A     * %3Cp%3E%0A     * A linear scan to find out which array the minimum value belongs to is expansive.%0A     * Can we return which array and the index together with the minimum value?%0A     * Sounds like another array.%0A     */%0A    public double getMedian(int%5B%5D%5B%5D arrs) %7B%0A        if (arrs.length == 0) return 0;%0A        // int%5B%5D is %7Brow, column, value%7D%0A        PriorityQueue%3Cint%5B%5D%3E pq = new PriorityQueue%3C%3E(arrs.length, Comparator.comparingInt(a -%3E a%5B2%5D));%0A        int n = 0; // Total number of integers.%0A        for (int i = 0; i %3C arrs.length; i++) %7B%0A            pq.offer(new int%5B%5D%7Bi, 0, arrs%5Bi%5D%5B0%5D%7D);%0A            n += arrs%5Bi%5D.length;%0A        %7D%0A%0A        /*%0A         * Note that median's definition is:%0A         * If total number is odd, median is the number right in the middle.%0A         * If total number is even, median is the average of the 2 numbers in the middle.%0A         */%0A        double median = 0;%0A        /*%0A         * When n = 2k+1, n/2 = k, loop runs k times. The next number is the median.%0A         * E.g. n = 7, n/2 = 3, the 4th number is the median.%0A         * When n = 2k, n/2 = k, loop runs k times.%0A         * E.g. n = 8, n/2 = 4, the average of 4th and 5th is
+Note that the median depends on whether we have odd or even total numbers, N.%0A     * If N is odd, median is the number at N / 2 + 1.%0A     * E.g. N = 7, N/2 = 3, the 4th number is the median.%0A     * If N is even, median is the average of N / 2 and N / 2 + 1.%0A     * E.g. N = 8, N/2 = 4, the average of 4th and 5th is the median.%0A     */%0A    public double getMedian(int%5B%5D%5B%5D arrs) %7B%0A        if (arrs.length == 0) return 0;%0A        // int%5B%5D is %7Brow, column, value%7D%0A        PriorityQueue%3Cint%5B%5D%3E pq = new PriorityQueue%3C%3E(arrs.length, Comparator.comparingInt(a -%3E a%5B2%5D));%0A        int n = 0; // Total number of integers.%0A        for (int i = 0; i %3C arrs.length; i++) %7B%0A            pq.offer(new int%5B%5D%7Bi, 0, arrs%5Bi%5D%5B0%5D%7D);%0A            n += arrs%5Bi%5D.length;%0A        %7D%0A%0A        double median = 0;%0A        for (int i = 0; i %3C n / 2; i++) %7B // Loop n / 2 times.%0A            // Get min from heap, then add its next to heap if
  the
- median.%0A         */%0A        for (int i = 0; i %3C n / 2; i++) %7B
+re is one.
 %0A   
@@ -1462,39 +1462,8 @@
 %5D++;
- // Move pointer one step back.
 %0A   
@@ -1509,25 +1509,8 @@
 1%5D%5D;
- // Update value.
 %0A   
@@ -1540,24 +1540,8 @@
 in);
- // Add to heap.
 %0A   

update MedianOfNSortedArrays explanation