Compute the closest entries in sorted arrays

Related: LeetCode 632 - Smallest Range (shortest range in k-sorted lists)

https://www.geeksforgeeks.org/find-smallest-range-containing-elements-from-k-lists/

Given k sorted lists of integers of size n each, find the smallest range that includes at least element from each of the k lists. If more than one smallest ranges are found, print any one of them.

Example :

Input:
K = 3
arr1[] : [4, 7, 9, 12, 15]
arr2[] : [0, 8, 10, 14, 20]
arr3[] : [6, 12, 16, 30, 50]
Output:
The smallest range is [6 8] 
Explanation: Smallest range is formed by 
number 7 from first list, 8 from second
list and 6 from third list.

A Better efficient approach is to use min heap. Below are the steps –

1. Create a min heap of size k and insert first elements of all k lists into the heap.
2. Maintain two variables min and max to store minimum and maximum values present in the heap at any point. Note min will always contain value of the root of the heap.
3. Repeat following steps
   • Get minimum element from heap (minimum is always at root) and compute the range.
   • Replace heap root with next element of the list from which the min element is extracted. After replacing the root, heapify the tree. Update max if next element is greater. If the list doesn’t have any more elements, break the loop

// A min heap node

struct MinHeapNode

{

    int element; // The element to be stored

    int i; // index of the list from which the element is taken

    int j; // index of the next element to be picked from list

};

void findSmallestRange(int arr[][N], int k)

{

    // Create a min heap with k heap nodes. Every heap node

    // has first element of an list

    int range = INT_MAX;

    int min = INT_MAX, max = INT_MIN;

    int start, end;

  

    MinHeapNode *harr = new MinHeapNode[k];

    for (int i = 0; i < k; i++)

    {

        harr[i].element = arr[i][0]; // Store the first element

        harr[i].i = i; // index of list

        harr[i].j = 1; // Index of next element to be stored

                       // from list

  

        // store max element

        if (harr[i].element > max)

            max = harr[i].element;

    }

  

    MinHeap hp(harr, k); // Create the heap

  

    // Now one by one get the minimum element from min

    // heap and replace it with next element of its list

    while (1)

    {

        // Get the minimum element and store it in output

        MinHeapNode root = hp.getMin();

  

        // update min

        min = hp.getMin().element;

  

        // update range

        if (range > max - min + 1)

        {

            range = max - min + 1;

            start = min;

            end = max;

        }

  

        // Find the next element that will replace current

        // root of heap. The next element belongs to same

        // list as the current root.

        if (root.j < N)

        {

            root.element = arr[root.i][root.j];

            root.j += 1;

  

            // update max element

            if (root.element > max)

                max = root.element;

        }

  

        // break if we have reached end of any list

        else break;

  

        // Replace root with next element of list

        hp.replaceMin(root);

    }




Compute the closest entries in three sorted arrays

http://www.careercup.com/question?id=14805690
Given 3 sorted arrays. Find(x,y,z), (where x is from 1st array, y is from 2nd array, and z is from 3rd array), such that Max(x,y,z) - Min(x,y,z) is minimum. 

public int minGap(int[] a, int[] b, int[] c) 
        {
                int diff = Integer.MAX_VALUE;
                int min = Integer.MAX_VALUE;
                int max = Integer.MIN_VALUE;
                int i, j, k;
                for(i = 0, j = 0, k = 0; i < a.length && j < b.length && k < c.length;) {
                        min = Math.min(a[i], Math.min(b[j], c[k]));
                        max = Math.max(a[i], Math.max(b[j], c[k]));
                        diff = Math.min(diff, max - min);
                        if(diff == 0) break;
                        if(a[i] == min) i++;
                        else if(b[j] == min) j++;
                        else k++;
                }
                return diff;
        }

MinimumDistance3SortedArrays.java
  public static int findMinDistanceSortedArrays(
      List<? extends List<Integer>> arrs) {
    // Pointers for each of arrs.
    List<Integer> idx = new ArrayList<>(arrs.size());
    for (List<Integer> arr : arrs) {
      idx.add(0);
    }
    int minDis = Integer.MAX_VALUE;
// contains arrs.size() elements
    NavigableSet<ArrData> currentHeads = new TreeSet<>();

    // Each of arrs puts its minimum element into current_heads.
    for (int i = 0; i < arrs.size(); ++i) {
      if (idx.get(i) >= arrs.get(i).size()) {
        return minDis;
      }
      currentHeads.add(new ArrData(i, arrs.get(i).get(idx.get(i))));
    }

    while (true) {
      minDis = Math.min(minDis, currentHeads.last().val
          - currentHeads.first().val);
      int tar = currentHeads.first().idx;
      // Return if there is no remaining element in one array.
      idx.set(tar, idx.get(tar) + 1);
      if (idx.get(tar) >= arrs.get(tar).size()) {
        return minDis;
      }
      currentHeads.pollFirst();
      currentHeads.add(new ArrData(tar, arrs.get(tar).get(idx.get(tar))));
    }
  }
  public static class ArrData implements Comparable<ArrData> {
    public int idx;
    public int val;

    public ArrData(int idx, int val) {
      this.idx = idx;
      this.val = val;
    }
    public int compareTo(ArrData o) {
      int result = Integer.valueOf(val).compareTo(o.val);
      if (result == 0) {
        result = Integer.valueOf(idx).compareTo(o.idx);
      }
      return result;
    }
  }