632. Smallest Range Covering Elements from K Lists (H)

Pinterest

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

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: nums = [[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].

Example 2:

Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]

Constraints:

• nums.length == k

• 1 <= k <= 3500

• 1 <= nums[i].length <= 50

• -105 <= nums[i][j] <= 105

• nums[i] is sorted in non-decreasing order.

Solution:

Version 1: Sliding Window

1. Sort the input lists to one sorted array.

2. Use two pointers to find the range which contains at least one element from each input list.

3. Find the shortest range from every candidate.

Example:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]

sorted array = [0, 4, 5, 9, 10, 12, 15, 18, 20, 22, 24, 26, 30]

l = 0, r = 0 =>   [0]              // Not match
l = 0, r = 1 =>   [0,4]            // Not match
l = 0, r = 2 =>   [0,4,5]          // Match, ans = [0,5]
l = 1, r = 3 =>   [4,5,9]          // Match, compare [4,9] with [0,5], ans = [0,5]
l = 2, r = 4 =>   [5,9,10]         // Match, compare [5,10] with [0,5], ans = [0,5]
l = 3, r = 7 =>   [9,10,12,15,18]  // Match, compare [9,18] with [0,5], ans = [0,5]
l = 4, r = 7 =>   [10,12,15,18]    // Match, compare [10,18] with [0,5], ans = [0,5]
l = 5, r = 7 =>   [12,15,18]       // Match, compare [12,18] with [0,5], ans = [0,5]
l = 6, r = 8 =>   [15,18, 20]      // Match, compare [15,20] with [0,5], ans = [0,5]
l = 7, r = 10 =>  [18,20,22,24]    // Match, compare [18,24] with [0,5], ans = [0,5]
l = 8, r = 10 =>  [20,22,24]       // Match, compare [20,24] with [0,5], ans = [20,24]
l = 9, r = 12 =>  [22,24,26,30]    // Not match
l = 10, r = 12 => [24,26,30]       // Not match
l = 11, r = 12 => [26,30]          // Not match
l = 12, r = 12 => [30]             // Not match

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {

        // Keep index of every element
        TreeMap<Integer, List<Integer>> map = new TreeMap<>();
        for(int i = 0; i< nums.size(); i++)
        {
            List<Integer> list = nums.get(i);
            for(Integer element: list)
            {
                if(!map.containsKey(element))
                {
                    map.put(element, new ArrayList<Integer>());
                }
                map.get(element).add(i);
            }
        }
        
        // Create a sorted array
        List<Integer> merged = new ArrayList<Integer>(map.keySet());
        
        // Initial the res with first and last element in the sorted array
        int[] res = new int[]{merged.get(0), merged.get(merged.size()-1)};
        
        // record how many elments in each bucket
        int[] bucket = new int[nums.size()];
        
        int right = 0;
        
       for(int left = 0; left < merged.size(); left++)
        {
            // Move right pointer until res has elements from all the buckets
            while(right < merged.size() && !IsFullBucket(bucket))
            {
                for(int bucketNum : map.get(merged.get(right)))
                {
                    bucket[bucketNum]++;
                }
                right++;
            }
            
            // Condition match
            if(IsFullBucket(bucket) && merged.get(right-1) - merged.get(left) < res[1] - res[0])
            {
                res[0] = merged.get(left);
                res[1] = merged.get(right-1);
            }
           
           // Remove left pointer element out of the bucket
           for(int m : map.get(merged.get(left)))
           {
               bucket[m]--;
           }
        }
        return res;
    }
    
    public boolean IsFullBucket(int[] bucket)
    {
        for(int element : bucket)
        {
            if(element == 0) return false;
        }
        return true;
    }
}

Version 2: Priority Queue

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.