Massive Algorithms: Shortest range covering all lists

Shortest range covering all lists - PrismoSkills

LeetCode 632 - Smallest Range
Shortest range covering all lists - PrismoSkills
Problem: Given N sorted lists, find smallest range of elements which represent one element from each list.

Solution:

We start by creating a min-heap and a max-heap of the first elements of each list.
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.
At every step in the loop, min and max in the heap are analyzed.
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.

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();
}
There is no need for two priority queues, minPQ is enough.

The maxPQ usage also slows down the solution asymptotically
because maxPQ.remove is linear.
https://github.com/mnorbi/algo-practice/blob/master/prismo/ShortestRangeCoveringAllLists.java
static int[] solve(int[][] mat){
Comparator<Cell> comp = (c1, c2) -> Integer.compare(mat[c1.row][c1.col], mat[c2.row][c2.col]);
Cell rangeStart = findRangeStart(mat, comp);
return createRange(mat, comp, rangeStart);
}

private static Cell findRangeStart(int[][] mat, Comparator<Cell> comp) {
int ROWS = mat.length;
int COLS = mat[0].length;
PriorityQueue<Cell> minPq = new PriorityQueue<>(comp);
minPq.add(new Cell(0, 0));
Cell max = minPq.peek();
for(int i = 1; i < ROWS; ++i){
Cell cell = new Cell(i, 0);
minPq.add(cell);
if (comp.compare(max, cell) < 0){
max = cell;
}
}
Cell ret = null;
int widthOpt = Integer.MAX_VALUE;
while(true){
Cell min = minPq.remove();
int width = mat[max.row][max.col]-mat[min.row][min.col];
if (widthOpt > width){
widthOpt = width;
ret = min;
}
if (min.col == COLS-1) break;
Cell cell = new Cell(min.row, min.col +1);
minPq.add(cell);
if (comp.compare(max, cell) < 0){
max = cell;
}
}
return ret;
}

private static int[] createRange(int[][] mat, Comparator<Cell> comp, Cell rangeStart) {
int ROWS = mat.length;
int[] ret = new int[ROWS];
PriorityQueue<Cell> minPq = new PriorityQueue<>(comp);
for(int i = 0; i < ROWS; ++i){
Cell cell = new Cell(i, 0);
minPq.add(cell);
}

for(int i = 0;;){
Cell min = minPq.peek();
if (min.row == rangeStart.row && min.col == rangeStart.col){
while(!minPq.isEmpty() ){
Cell cell = minPq.remove();
ret[i++] = mat[cell.row][cell.col];
}
return ret;
}
minPq.remove();
Cell cell = new Cell(min.row, min.col+1);
minPq.add(cell);
}
}
class Cell {
int row, col;
Cell(int row, int col){
this.row = row;
this.col = col;
}
}

http://www.fgdsb.com/2015/01/17/smallest-range/

You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.

For example,
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]

The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.

G家题，实际上就是k路归并的变种题。维护一个长度为n的min heap（n为数组个数），每次找一个最小的，同时保持记录一个最大的。
比如那个例子：
heap初始化为[0,4,5]，min = 0, max = 5，当前最小range为[0,5]。
pop掉最小的再push，[4,5,9]，min = 4, max = 9，当前最小range还是[0,5]。
继续，[5,9,10]，min = 5, max = 10，当前最小range还是[0,5]。
继续，[9,10,18]，min = 9, max = 18，当前最小range还是[0,5]。
继续，[10,12,18]，min = 10, max = 18，当前最小range还是[0,5]。
继续，[12,15,18]，min = 12, max = 18，当前最小range还是[0,5]。
继续，[15,18,20]，min = 15, max = 20，当前最小range还是[0,5]。
继续，[18,20,24]，min = 18, max = 24，当前最小range还是[0,5]。
继续，[20,22,24]，min = 20, max = 24，当前最小range变成[20,24]。
依次类推，最小范围为[20,24]。


pair<int,int> min_range(const vector<vector<int>>& nums) {

// first: array id, second: element id

using _pair = pair<int,int>;

priority_queue<_pair,vector<_pair>,function<bool(_pair&,_pair&)>> heap {

[&](_pair& a, _pair& b) { return nums[a.first][a.second] >= nums[b.first][b.second]; }

};



int cur_max = INT_MIN;

for(auto i = 0; i < nums.size(); ++i) {

if(nums[i].empty()) continue;

heap.emplace(i, 0);

cur_max = std::max(cur_max, nums[i][0]);

}

if(heap.empty()) return {-1, -1};



int begin = nums[heap.top().first][heap.top().second];

int min_len = cur_max - begin;



while (heap.size() == nums.size()) {

auto top = heap.top();

heap.pop();

if(top.second + 1 < nums[top.first].size()) {

int new_begin = nums[heap.top().first][heap.top().second];

int new_num = nums[top.first][top.second + 1];

new_begin = std::min(new_begin, new_num);

cur_max = std::max(cur_max, new_num);

if(cur_max - new_begin < min_len) {

begin = new_begin;

min_len = cur_max - new_begin;

}

heap.emplace(top.first, top.second + 1);

}

}

return {begin, begin + min_len};

}

http://massivealgorithms.blogspot.com/2014/11/shortest-range-covering-all-lists.html

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);

    }

    cout << "The smallest range is " << "["

         << start << " " << end << "]" << endl;;

}

https://gist.github.com/elderdigiuseppe/6224350
http://algorithms.tutorialhorizon.com/shortest-range-in-k-sorted-lists/

Related: Find the smallest subarray covering all values - EPI
Read full article from Shortest range covering all lists - PrismoSkills

Shortest range covering all lists - PrismoSkills

Labels

Popular Posts