Make delicious recipes!

Shortest range covering all lists



Problem: Given N sorted lists, find smallest range of elements which represent one element from each list.

Example:
Consider the below given lists:

 Line 1:  17, 35, 63,
 Line 2:  18, 26, 66,
 Line 3:  42, 48, 90,
 Line 4:  26, 33, 39,
 Line 5:  36, 68, 72,

The shortest range of elements which represents one 
element from each list in the above is:

26(Line 3)
26(Line 1)
35(Line 0)
36(Line 4)
42(Line 2)

Solution:
  1. We start by creating a min-heap and a max-heap of the first elements of each list.
  2. In a loop,
    1. One element from the min-heap is removed and
    2. Next element from the corresponding list is put into the heap.
  3. At every step in the loop, min and max in the heap are analyzed.
  4. If their difference is lesser than the current minimum, then a new minimum is selected.

While this looks simple enough, note that currently Java does not provide a Double-Ended-Priority-Queue.
So we cannot get the minimum and maximum with just one heap.

This is fixed by creating two heaps - min and max heap.
During removing, minimum element is removed from min-heap but from max-heap, element is removed by reference.

To improve performance, every integer data from the lists is wrapped into an object which also stores the line-number of the list.
With this scheme, it is easy to load the next number from that list whose element is polled from the min-heap.

Code:

import java.util.*;

public class ShortestRangeCoveringAllLists 
{

    // Wrapper class to store line-number along with the integer data in the Heap    
    public static class DataAndLineNum
    {
        public int data;
        public int lineNum;
    }
    
    
    // Ascending Comparator
    public static class DateLineComparator implements Comparator<DataAndLineNum>
    {
        @Override
        public int compare(DataAndLineNum o1, DataAndLineNum o2) 
        {
                return o1.data - o2.data;
        }
    }
    
    
    // Descending comparator
    public static class DateLineReverseComparator implements Comparator<DataAndLineNum>
    {
        @Override
        public int compare(DataAndLineNum o1, DataAndLineNum o2) 
        {
                return o2.data - o1.data;
        }
    }
    
    public static void main(String[] args) 
    {
        // Get some random input data
        int numLists = 5;
        int listSize = 4;
        Object lists[] = getRandomSortedLists (numLists, listSize);
        
        // Create ascending and descending comparators
        DateLineComparator cmp = new DateLineComparator ();
        DateLineReverseComparator revCmp = new DateLineReverseComparator();
        
        // Create min-Heap and max-Heap by using PriorityQueue
        PriorityQueue <DataAndLineNum> minPQ = new PriorityQueue<DataAndLineNum>(numLists, cmp);
        PriorityQueue <DataAndLineNum> maxPQ = new PriorityQueue<DataAndLineNum>(numLists, revCmp);
        
        // Put first element of each list into min-Heap and max-Heap
        // Each element is converted from normal integer to wrapper class DataAndLineNum before inserting     
        for (int i=0; i<numLists; i++)
        {
            ArrayList<Integer> lst = (ArrayList<Integer>) lists[i];
            
            DataAndLineNum info = new DataAndLineNum();
            info.data = lst.get(0);
            info.lineNum = i;
            
            minPQ.add(info);
            maxPQ.add(info);
        }
        
        
        // Heaps are initialized with first element of each list.
        // Now, remove one element from min-Heap and remove corresponding element from max-Heap
        // From the removed element, get the line number
        // From the line-number, go directly to the list and take the next element from it.
        
        int minDiff = 0;
        
        while (minPQ.size() > 0)
        {
            if (minPQ.size() == numLists)
            {
                int diff = maxPQ.peek().data - minPQ.peek().data; 
                if (minDiff == 0 || diff < minDiff)
                {
                    minDiff = diff;
                    printCurrentPQ (minPQ, minDiff);
                }
            }
                
            DataAndLineNum smallest = minPQ.poll(); // remove smallest from min-Heap
            maxPQ.remove(smallest);                 // remove same element from max-Heap
            
            
            // get next number from the line whose element is removed above
            int lineNum = smallest.lineNum;
            ArrayList<Integer> list = (ArrayList<Integer>) lists[lineNum];
            list.remove(0);
            
            if (list.size() > 0)
            {
                smallest.data = list.get(0); // re-use the wrapper object smallest
                minPQ.add(smallest);
                maxPQ.add(smallest);
            }
        }
    }
    
    
    
    

    // Helper method to print the priority queue
    static void printCurrentPQ(PriorityQueue<DataAndLineNum> pq, int minDiff) 
    {
        System.out.print("Diff = " + minDiff);
        System.out.println();
        
        DataAndLineNum []arr = new DataAndLineNum[pq.size()];
        int i=0;
        while (pq.size() > 0)
        {
            arr[i++] = pq.poll();
            System.out.println(arr[i-1].data + "(Line " + arr[i-1].lineNum + ")");
        }
        for (DataAndLineNum d : arr)
            pq.add(d);
        System.out.println();
    }


    

    // Helper method to generate 'numLists' sorted lists, each of size 'listSize'
    static Object[] getRandomSortedLists(int numLists, int listSize) 
    {
        Object lists[] = new Object [numLists];
        for (int i=0; i<numLists; i++)
        {
            ArrayList <Integer> lst = new ArrayList<Integer> ();
            for (int j=0; j<listSize; j++)
                lst.add((int)(10 + Math.random()*89));
            
            Object [] arr = lst.toArray();
            Arrays.sort(arr);
            lst.clear();
            
            for (Object j: arr)
                lst.add((Integer)j);
            
            lists[i] = lst;
        }
        
        
        for (int i=0; i<numLists; i++)
        {
            ArrayList <Integer> lst = (ArrayList <Integer>)lists[i];
            for (int j : lst)
                System.out.print(j + ", ");
            System.out.println();
        }
        System.out.println();
        return lists;
    }

}



Sample Execution:

Input Lists:
15, 59, 70, 95, 
35, 41, 55, 91, 
22, 54, 57, 60, 

Every time a new minimum is found, the range is printed

Diff = 20
  15(Line 0)
  22(Line 2)
  35(Line 1)

Diff = 18
  41(Line 1)
  54(Line 2)
  59(Line 0)

Diff = 5
  54(Line 2)
  55(Line 1)
  59(Line 0)

Diff = 4
  55(Line 1)
  57(Line 2)
  59(Line 0)







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal