Java Code using TreeSet


  • 0
    B

    The idea is to use remove the smallest element in the Tree until we hit the last element of a list.

      public int[] smallestRange(List<List<Integer>> nums) {
        int[] result = new int[2];
        TreeSet<Pair> tree = new TreeSet<>();
        for (List<Integer> list : nums) {
          tree.add(new Pair(list));
        }
        int smallestRange = Integer.MAX_VALUE;
        while (true) {
          Pair first = tree.first();
          Pair last = tree.last();
          if (last.getValue() - first.getValue() < smallestRange) {
            smallestRange = last.getValue() - first.getValue();
            result[0] = first.getValue();
            result[1] = last.getValue();
          }
          Pair pair = tree.pollFirst();
          if (pair.increment()) {
            tree.add(pair);
          } else {
            break;
          }
        }
        return result;
      }
    
      public static class Pair implements Comparable<Pair> {
        private List<Integer> list;
        private int index;
    
        public Pair(List<Integer> list) {
          this.list = list;
        }
    
        public boolean increment() {
          if (index < list.size() - 1) {
            ++index;
            return true;
          }
          return false;
        }
    
        public int getValue() {
          return list.get(index);
        }
    
        @Override
        public int compareTo(Pair o) {
          int i = list.get(index) - o.list.get(o.index);
          return i == 0 ? 1 : i;
        }
      }
    

Log in to reply
 

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