Java Sliding Window solution (Similar to Longest Substring with At Most K Distinct Characters)


  • 0
    C
    public int[] smallestRange(List<List<Integer>> nums) {
            int[] res = new int[2];
            int k=nums.size();
            List<int[]> list = new ArrayList<int[]>();
            for(int i=0; i<k; i++){
                for(int j=0; j<nums.get(i).size(); j++){
                    list.add(new int[]{nums.get(i).get(j), i});
                }
            }
            Collections.sort(list, new Comparator<int[]>(){
                public int compare(int[] a, int[] b){
                    return a[0]-b[0];
                }
            });
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
            int minRange=Integer.MAX_VALUE;
            int start=0;
            for(int i=0; i<list.size(); i++){
                int[] cur=list.get(i);
                map.put(cur[1], map.getOrDefault(cur[1],0)+1);
                while(map.size()==k){
                    int prev=list.get(start)[1];
                    if(map.get(prev)==1)
                        break;
                    map.put(prev, map.get(prev)-1);
                    start++;
                }
                if(map.size()==k && minRange>cur[0]-list.get(start)[0]){
                    int min=list.get(start)[0];
                    minRange=cur[0]-min;
                    res[0]=min;
                    res[1]=cur[0];
                }
            }
            return res; 
        }
    

Log in to reply
 

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