Java solution using Sliding Window


  • 0
    S

    Here I use a sliding window to keep the potential answer.

    1. Use a TreeMap<Integer, Set<Integer>> to store all elements in each list. The key for this map is the value of each element in lists, the value of this map is a set that contains index of which list does this element come from.
      For example, lists = [[1,2,3], [2,4,5], [2,4,7,8]], then the map will be:
      [1] -> {0}
      [2] -> {0,1,2}
      [3] -> {0}
      [4] -> {1,2}
      [5] -> {1}
      [7] -> {2}
      [8] -> {2}

    2. Use two pointers to make up a sliding window, when the number of distinct lists in the window is less than lists.size(), we keep moving right pointer further (expand).

    3. When the number of distinct lists in the window is equal to lists.size(), we can move left pointer (shrink) to find a minimum length of this window.

        public int[] smallestRange(List<List<Integer>> nums) {
            // <value, corresponding index in nums>
            TreeMap<Integer, Set<Integer>> map = new TreeMap<>();
            int[] count = new int[nums.size()];
            Set<Integer> numOfLists = new HashSet<>();
            List<Integer> res = new ArrayList<>(2);
    
            for (int i=0; i<nums.size(); i++) {
                for (int num : nums.get(i)) {
                    if (!map.containsKey(num)) {
                        map.put(num, new HashSet<Integer>());
                    }
                    map.get(num).add(i);
                }
            }
    
            Integer left = map.firstKey();
            Integer right = map.firstKey();
    
            while (right != null) {
                // Add right pointer into window
                Set<Integer> indices = map.get(right);
                for (int index : indices) {
                    count[index]++;
                    numOfLists.add(index);
                }
    
                // If every list is covered, shrink the window by move left pointer
                while (numOfLists.size() == nums.size() && left<=right) {
                    if (res.isEmpty() || res.get(1)-res.get(0) > right-left) {
                        res.clear();
                        res.add(left);
                        res.add(right);
                    }
    
                    Set<Integer> leftIndices = map.get(left);
                    for (int index : leftIndices) {
                        if (--count[index] == 0) {
                            numOfLists.remove(index);
                        }
                    }
                    left = map.higherKey(left);
                }
                right = map.higherKey(right);
            }
    
            return res.isEmpty() ? new int[0] : new int[] {res.get(0), res.get(1)};
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.