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

https://leetcode.com/problems/smallest-range

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

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:

1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= k <= 3500
3. -105 <= value of elements <= 105.
4. For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.

https://leetcode.com/articles/smallest-range/
X.
https://www.acwing.com/solution/leetcode/content/486/
(多指针，堆) O(nlogk)O(nlog⁡k)
可以很容易的看出，答案的区间左右端点一定是某两个序列中的某两个数。
初始化 k 个指针指向每个列表的首元素，并将其和所在列表的序号合并为 pair 加入到小根堆中，并记录这 k 个数的最大值。
每次从小根堆中弹出最小值，和此时的最大值构成的区间就构成一个候选的答案。
接着，最小值所在列表的指针向后移动，加入新的数字到堆中，并更新此时的最大值。
不断按照以上操作，直到某个指针到达了序列末尾为止。
时间复杂度
堆的大小为 O(k)O(k)，在遍历所有数字时都会进行对堆的操作，故时间复杂度为 O(nlogk)O(nlog⁡k)。

求k个数组的最大值和最小值的过程，可以用大小为k的优先队列（最小堆）来优化，复杂度可以降为O(nlgk)

类似归并排序思想——多维有序数组问题考虑mergeSort+pq思想

pq内每次poll出当前最小值，max保存当前已访问的最大值，当前pq中的所有值一定在这个区间内（满足该区间覆盖所有数组条件），只要看这个区间是否为更小的那个区间即可

https://discuss.leetcode.com/topic/94445/java-code-using-priorityqueue-similar-to-merge-k-array

Image you are merging k sorted array using a heap. Then everytime you pop the smallest element out and add the next element of that array to the heap. By keep doing this, you will have the smallest range.

public int[] smallestRange(int[][] nums) {
  PriorityQueue<Element> pq = new PriorityQueue<Element>(new Comparator<Element>() {
   public int compare(Element a, Element b) {
    return a.val - b.val;
   }
  });
  int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
  for (int i = 0; i < nums.length; i++) {
   Element e = new Element(i, 0, nums[i][0]);
   pq.offer(e);
   max = Math.max(max, nums[i][0]);
  }
  int range = Integer.MAX_VALUE;
  int start = -1, end = -1;
  while (pq.size() == nums.length) {

   Element curr = pq.poll();
   if (max - curr.val < range) {
    range = max - curr.val;
    start = curr.val;
    end = max;
   }
   if (curr.idx + 1 < nums[curr.row].length) {
    curr.idx = curr.idx + 1;
    curr.val = nums[curr.row][curr.idx];
    pq.offer(curr);
    if (curr.val > max) {
     max = curr.val;
    }
   }
  }

  return new int[] { start, end };
 }

 class Element {
  int val;
  int idx;
  int row;

  public Element(int r, int i, int v) {
   val = v;
   idx = i;
   row = r;
  }
 }

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

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.

https://leetcode.com/articles/smallest-range/

    public int[] smallestRange(int[][] nums) {
        int minx = 0, miny = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        int[] next = new int[nums.length];
        boolean flag = true;
        PriorityQueue < Integer > min_queue = new PriorityQueue < Integer > ((i, j) -> nums[i][next[i]] - nums[j][next[j]]);
        for (int i = 0; i < nums.length; i++) {
            min_queue.offer(i);
            max = Math.max(max, nums[i][0]);
        }
        for (int i = 0; i < nums.length && flag; i++) {
            for (int j = 0; j < nums[i].length && flag; j++) {
                int min_i = min_queue.poll();
                if (miny - minx > max - nums[min_i][next[min_i]]) {
                    minx = nums[min_i][next[min_i]];
                    miny = max;
                }
                next[min_i]++;
                if (next[min_i] == nums[min_i].length) {
                    flag = false;
                    break;
                }
                min_queue.offer(min_i);
                max = Math.max(max, nums[min_i][next[min_i]]);
            }
        }
        return new int[] { minx, miny};
    }

https://leetcode.com/problems/smallest-range/discuss/231024/Java-Easy-to-understand-nlog(k)-beets-97

    public int[] smallestRange(List<List<Integer>> nums) {
        if(nums == null || nums.isEmpty()) {
            return null;
        }
        
        PriorityQueue<IntItr> minpq = new PriorityQueue<>(new Comparator<IntItr>(){
            public int compare (IntItr a, IntItr b) {
                return a.cur - b.cur;
            }
        });
        
        int maxValue = Integer.MIN_VALUE;
        for (List<Integer> list : nums) {
            IntItr intitr = new IntItr(list.listIterator());
            minpq.add(intitr);
            maxValue = Math.max(maxValue, intitr.getCur());
        }
        
        int range = Integer.MAX_VALUE;
        int[] result = new int[2];
        
        
        while(minpq.size() == nums.size()) {
            if (maxValue - minpq.peek().cur < range) {
                range = maxValue - minpq.peek().cur;
                result[0] = minpq.peek().cur;
                result[1] = maxValue;
            }
            IntItr min = minpq.poll();
            if(min.hasNext()) {
                min.next();
                minpq.add(min);
                maxValue = Math.max(maxValue, min.getCur());
            }
            
        }
        
        return result;
    }
    
    public class IntItr{
        int cur;
        Iterator itr;
        public IntItr(ListIterator<Integer> iterator) {
            itr = iterator;
            cur = (Integer)itr.next();
        }
        
        public int getCur() {
            return cur;
        }
        
        public void next() {
            cur = (Integer)itr.next();
        }
        
        public boolean hasNext() {
            return itr.hasNext();
        }
    }

X. Using minQueue and maxQueue
http://prismoskills.appspot.com/lessons/Algorithms/Chapter_07_-_Shortest_range_with_all_lists.jsp
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);
}
}

X. Sliding windows
https://discuss.leetcode.com/topic/94589/java-8-sliding-window

The idea is to sort all the elements in the k lists and run a sliding window over the sorted list, to find the minimum window that satisfies the criteria of having atleast one element from each list.

public static int[] smallestRange(List<List<Integer>> nums) {
        List<int[]> list = IntStream.range(0, nums.size())
                .mapToObj( i -> nums.get(i).stream().map(x -> new int[]{x, i}))
                .flatMap(y -> y)
                .sorted(Comparator.comparingInt(p -> p[0])).collect(toList());
        int[] counts = new int[nums.size()];
        BitSet set = new BitSet(nums.size());
        int start = -1;
        int[] res = new int[2];
        for(int i = 0; i < list.size(); i++) {
            int[] p = list.get(i);
            set.set(p[1]);
            counts[p[1]] += 1;
            if(start == -1) { start = 0; }
            while(start < i && counts[list.get(start)[1]] > 1) {
                counts[list.get(start)[1]]--;
                start++;
            }
            if(set.cardinality() == nums.size()) {
                if( (res[0] == 0 && res[1] == 0) || (list.get(i)[0] - list.get(start)[0]) < res[1] - res[0]) {
                    res[0] = list.get(start)[0];
                    res[1] = list.get(i)[0];
                }
            }
        }
        return res;
    }

X. O(nlogn) Sliding window + two pointers
https://blog.csdn.net/fuxuemingzhu/article/details/82932656
这个题是76. Minimum Window Substring的变形，第76题要我们查找出s中一个最小的窗口，使得这个窗口中包含t的所有字符。如果把本题的nums中的每个数组合并成一个总的数组，那么就是找出一个小的窗口，使得这个窗口包含有不同区间的最少一个字符。

所以把nums放到一个数组里面去，放的过程中需要把这个数组的索引号也放进去。然后就可以通过查找出一个小的区间，这个区间里包含所有数组的索引号了。就是第76题。

使用right指针向右搜索，同时要记录在left～right这个区间内包含的数组个数和。如果在[left,right]区间内，数组个数和的个数和与原始数组个数相等了，说明在这个区间是符合要求的一个区间，但是不一定是最短区间。

因此，现在要移动left指针，要求，在[left, right]区间内的数组出现个数应该把所有的数组个数都进行包含。同样使用cnt来验证是否包含了所有的数组。

在移动left指针的时候要注意存储最短的区间，当所有的循环都结束之后最短区间即为题目要求了。

这个题使用字典保存不同数组出现的次数，以此来维护cnt。

这个题是寻找子字符串的模板题，应该记住。
http://www.cnblogs.com/grandyang/p/7200016.html
这道题给了我们一些数组，都是排好序的，让我们求一个最小的范围，使得这个范围内至少会包括每个数组中的一个数字。虽然每个数组都是有序的，但是考虑到他们之间的数字差距可能很大，所以我们最好还是合并成一个数组统一处理比较好，但是合并成一个大数组还需要保留其原属数组的序号，所以我们大数组中存pair对，同时保存数字和原数组的序号。然后我们重新按照数字大小进行排序，这样我们的问题实际上就转换成了求一个最小窗口，使其能够同时包括所有数组中的至少一个数字。这不就变成了那道Minimum Window Substring。所以说啊，这些题目都是换汤不换药的，总能变成我们见过的类型。我们用两个指针left和right来确定滑动窗口的范围，我们还要用一个哈希表来建立每个数组与其数组中数字出现的个数之间的映射，变量cnt表示当前窗口中的数字覆盖了几个数组，diff为窗口的大小，我们让right向右滑动，然后判断如果right指向的数字所在数组没有被覆盖到，cnt自增1，然后哈希表中对应的数组出现次数自增1，然后我们循环判断如果cnt此时为k(数组的个数)且left不大于right，那么我们用当前窗口的范围来更新结果，然后此时我们想缩小窗口，通过将left向右移，移动之前需要减小哈希表中的映射值，因为我们去除了数字，如果此时映射值为0了，说明我们有个数组无法覆盖到了，cnt就要自减1。这样遍历后我们就能得到最小的范围了

    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<int> res;
        vector<pair<int, int>> v;
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            for (int num : nums[i]) {
                v.push_back({num, i});
            }
        }
        sort(v.begin(), v.end());
        int left = 0, n = v.size(), k = nums.size(), cnt = 0, diff = INT_MAX;
        for (int right = 0; right < n; ++right) {
            if (m[v[right].second] == 0) ++cnt;
            ++m[v[right].second];
            while (cnt == k && left <= right) {
                if (diff > v[right].first - v[left].first) {
                    diff = v[right].first - v[left].first;
                    res = {v[left].first, v[right].first};
                } 
                if (--m[v[left].second] == 0) --cnt;
                ++left;
            }
        }
        return res;
    }

http://bookshadow.com/weblog/2017/07/02/leetcode-smallest-range/

解法I 滑动窗口（Sliding Window）

字典dmap维护映射num -> set(idx)，记录num在哪些列表（编号0~len(nums)）中出现过

字典cover维护映射idx -> set(num)，记录当前窗口覆盖了哪些列表，以及这些列表中包含的数字

snum为nums去重和排序的结果

初始令窗口范围start = end = 0

重复以下过程，直到start == len(snum) 或者end == len(snum)为止

  令end向右滑动，直到cover中包含所有列表为止

  令start向右滑动，直到cover中不再包含所有列表为止，并更新最小间隔和答案

https://discuss.leetcode.com/topic/96509/c-45ms-o-n-space-o-n-time-sol-without-priority-queue-iterators-just-vectors

The idea is storing all elements in a single array as pairs<number, list come from>. And then traverse the list using two pointer methods to find the smallest range.

    vector<int> smallestRange(vector<vector<int>>& nums) { 
        vector<pair<int, int>> data;   // first: number, second: the list the num comes from
        vector<int> hascover(nums.size(), 0);  // num of elements from each list in current range
        vector<int> result;

        for (int i=0; i<nums.size(); i++) {
            for (int each: nums[i]) {
                data.push_back({each, i});
            }
        }  
        sort(data.begin(), data.end());

        int minindex = 0;
        int mindiff = INT_MAX;
        int count = nums.size();  // nums of lists are in the range, 0 means all
        
        for (int i=0; i<data.size(); i++) {
            if (hascover[data[i].second] == 0) count--;
            hascover[data[i].second]++;
            
            while (count==0 && minindex <= i) {
                int minnum = data[minindex].first;
                int maxnum = data[i].first;
                if (maxnum - minnum < mindiff) {
                    mindiff = maxnum - minnum;
                    result.clear();
                    result.push_back(minnum);
                    result.push_back(maxnum);
                }
                hascover[data[minindex].second]--;
                if (hascover[data[minindex].second] == 0) count++;
                minindex++;
            }
        }
        return result;
    }




X.
http://code.bitjoy.net/2017/07/02/leetcode-smallest-range/

要求区间最小，则区间只包括每个数组的一个元素最好，所以我们要找k个数组中的k个数，使得这k个数的最大值和最小值的差最小，那么这个区间的两个端点就是这个最大值和最小值。

所以我们对k个数组维护k个指针，初始时都指向每个数组的首元素，然后找到这k个数的最大值和最小值，得到一个区间及其长度。然后我们不断循环：向前移动k个指针中的最小者，在新的k个数中求最大值和最小值及其区间长度。直到某个数组遍历结束，则返回得到的最小区间。

    vector<int> smallestRange(vector<vector<int>>& nums) {

        int ansmin = 0, ansmax = 0, ansrange = INT_MAX, k = nums.size();

        vector<int> ptr(k, 0);

        while (true) {

            bool done = false;

            int curmin = INT_MAX, curmax = INT_MIN, minid = 0;

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

                if (ptr[i] >= nums[i].size()) {

                    done = true;

                    break;

                }

                if (nums[i][ptr[i]] < curmin) {

                    curmin = nums[i][ptr[i]];

                    minid = i;

                }

                if (nums[i][ptr[i]] > curmax) {

                    curmax = nums[i][ptr[i]];

                }

            }

            if (done)break;

            if (curmax - curmin < ansrange) {

                ansrange = curmax - curmin;

                ansmin = curmin;

                ansmax = curmax;

            }

            ++ptr[minid];

        }

        return{ ansmin,ansmax };

    }

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

The idea is to maintain pointers to every list using array ptr[k].Below are the steps :

1. Initially the index of every list is 0,therefore initialize every element of ptr[0..k] to 0;
2. Repeat the following steps until atleast one list exhausts :
• Now find the minimum and maximum value among the current elements of all the list pointed by the ptr[0…k] array.
• Now update the minrange if current (max-min) is less than minrange.
• increment the pointer pointing to current minimum element.

Time complexity : O(n2 k)

// array for storing the current index of list i

int ptr[501];

// This function takes an k sorted lists in the form of

// 2D array as an argument. It finds out smallest range

// that includes elements from each of the k lists.

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

{

      int i,minval,maxval,minrange,minel,maxel,flag,minind;

       

      //initializing to 0 index;

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

        ptr[i] = 0;

      minrange = INT_MAX;

       

      while(1)      

      {

          // for mainting the index of list containing the minimum element

          minind = -1;

          minval = INT_MAX;

          maxval = INT_MIN;

          flag = 0;

          //iterating over all the list

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

          {   

              // if every element of list[i] is traversed then break the loop

              if(ptr[i] == n)  

              {

                flag = 1;

                break;

              }

              // find minimum value among all the list elements pointing by the ptr[] array

              if(ptr[i] < n && arr[i][ptr[i]] < minval) 

              {

                  minind=i;  // update the index of the list

                  minval=arr[i][ptr[i]];

              }

              // find maximum value among all the list elements pointing by the ptr[] array

              if(ptr[i] < n && arr[i][ptr[i]] > maxval)   

              {

                  maxval = arr[i][ptr[i]];

              }

          }

          //if any list exhaust we will not get any better answer ,so break the while loop

          if(flag)

            break;

          ptr[minind]++;

          //updating the minrange

          if((maxval-minval) < minrange) 

          {

              minel = minval;

              maxel = maxval;

              minrange = maxel - minel;

          }

      }

       

      printf("The smallest range is [%d , %d]\n",minel,maxel);

}

The naive approach is to consider every pair of elements, $nums[i][j]$ and $nums[k][l]$ from amongst the given lists and consider the range formed by these elements. For every range currently considered, we can traverse over all the lists to find if atleast one element from these lists can be included in the current range. If so, we store the end-points of the current range and compare it with the previous minimum range found, if any, satisfying the required criteria, to find the smaller range from among them.
Time complexity : $O(n^3)$. Considering every possible range(element pair) requires $O(n^2)$ time. For each range considered, we need to traverse over all the elements of the given lists in the worst case requiring another $O(n)$ time. Here, $n$ refers to the total number of elements in the given lists.



http://algorithms.tutorialhorizon.com/shortest-range-in-k-sorted-lists/

X. Brute Force
https://leetcode.com/articles/smallest-range/

The naive approach is to consider every pair of elements, $nums[i][j]$ and $nums[k][l]$ from amongst the given lists and consider the range formed by these elements. For every range currently considered, we can traverse over all the lists to find if atleast one element from these lists can be included in the current range. If so, we store the end-points of the current range and compare it with the previous minimum range found, if any, satisfying the required criteria, to find the smaller range from among them.

Once all the element pairs have been considered as the ranges, we can obtain the required minimum range.

Time complexity : $O(n^3)$. Considering every possible range(element pair) requires $O(n^2)$ time. For each range considered, we need to traverse over all the elements of the given lists in the worst case requiring another $O(n)$ time. Here, $n$ refers to the total number of elements in the given lists.

  public int[] smallestRange(int[][] nums) {

    int minx = 0, miny = Integer.MAX_VALUE;

    for (int i = 0; i < nums.length; i++) {

      for (int j = 0; j < nums[i].length; j++) {

        for (int k = i; k < nums.length; k++) {

          for (int l = (k == i ? j : 0); l < nums[k].length; l++) {

            int min = Math.min(nums[i][j], nums[k][l]);

            int max = Math.max(nums[i][j], nums[k][l]);

            int n, m;

            for (m = 0; m < nums.length; m++) {

              for (n = 0; n < nums[m].length; n++) {

                if (nums[m][n] >= min && nums[m][n] <= max)

                  break;

              }

              if (n == nums[m].length)

                break;

            }

            if (m == nums.length) {

              if (miny - minx > max - min || (miny - minx == max - min && minx > min)) {

                miny = max;

                minx = min;

              }

            }

          }

        }

      }

    }

    return new int[] { minx, miny };

  }

Time complexity : $O\big(n^2log(k)\big)$. The time required to consider every possible range is $O(n^2)$. For every range currently considered, a Binary Search requiring $O\big(log(k)\big)$ time is required. Here, $n$ refers to the total number of elements in the given lists and $k$ refers to the average length of each list.

  public int[] smallestRange(int[][] nums) {

    int minx = 0, miny = Integer.MAX_VALUE;

    for (int i = 0; i < nums.length; i++) {

      for (int j = 0; j < nums[i].length; j++) {

        for (int k = i; k < nums.length; k++) {

          for (int l = (k == i ? j : 0); l < nums[k].length; l++) {

            int min = Math.min(nums[i][j], nums[k][l]);

            int max = Math.max(nums[i][j], nums[k][l]);

            int n, m;

            for (m = 0; m < nums.length; m++) {

              n = Arrays.binarySearch(nums[m], min);

              if (n < 0)

                n = -1 - n;

              if (n == nums[m].length || nums[m][n] < min || nums[m][n] > max)

                break;

            }

            if (m == nums.length) {

              if (miny - minx > max - min || (miny - minx == max - min && minx > min)) {

                miny = max;

                minx = min;

              }

            }

          }

        }

      }

    }

    return new int[] { minx, miny };

  }