# Java Two Solutions, PriorityQueue and Sliding Window

• Method 1:
first put the smallest element of each list into the priorityqueue
poll the smallest one and add it's successor in its own list into priorityqueue so we can potentially increase the lower bound and reduce the window length.
keep doing this till we run out of elements for one of the list.

``````   public int[] smallestRange(List<List<Integer>> nums) {
PriorityQueue<int[]> minheap = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int k = nums.size(), len = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
int[] ans = null;
for (int i = 0; i < k; i++) {
int n = nums.get(i).get(0);
max = Math.max(max, n);
}
while (minheap.size() == k) {
int[] min = minheap.poll();
if (len > max-min[0]+1) {
len = max-min[0]+1;
ans = new int[]{min[0], max};
}
if (min[1] < nums.get(min[2]).size()-1) {
int n = nums.get(min[2]).get(min[1]+1);
max = Math.max(max, n);
}
}
return ans;
}
``````

Method 2:
combine all the elements into a single list and discard duplicates from the same list, this is nlogk if we use a minheap.
using sliding window similar to 76. Minimum Window Substring to get the smallest window.

``````    public int[] smallestRange(List<List<Integer>> nums) {
ArrayList<int[]> list = new ArrayList<>();
int k = nums.size(), len = Integer.MAX_VALUE;
PriorityQueue<int[]> minheap = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
for (int i = 0; i < k; i++) {
}
while (!minheap.isEmpty()) {
int[] min = minheap.poll();
int i = min[1]+1;
List<Integer> l = nums.get(min[2]);
while (i < l.size() && l.get(i) == l.get(min[1])) i++;
if (i < l.size()) minheap.add(new int[]{l.get(i), i, min[2]});
}
int[] count = new int[k], ans = null;
for (int i = 0, j = 0, n = 0; i < list.size(); i++) {
int[] a = list.get(i);
if (count[a[2]]++ == 0 && ++n == k) {
while (--count[list.get(j++)[2]] > 0);
n--;
if (len > a[0]-list.get(j-1)[0]+1) {
len = a[0]-list.get(j-1)[0]+1;
ans = new int[]{list.get(j-1)[0], list.get(i)[0]};
}
}
}
return ans;
}
``````

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