Java Solution using a TreeSet


  • 0
    G
    public class Solution {
        
        public static class Pair{
            int i1;
            int i2;
            
            public Pair(int i, int j){
                i1 = i;
                i2 = j;
            }
        }
        
        public int[] smallestRange(List<List<Integer>> nums) {
            
            TreeSet<Pair> s = new TreeSet<>(new Comparator<Pair>(){
                public int compare(Pair i, Pair j){
                    
                    int temp = nums.get(i.i1).get(i.i2) - nums.get(j.i1).get(j.i2);
                    
                     if(temp < 0){
                         return -1;
                     }
                     else if(temp == 0)
                     {
                         return i.i1 - j.i1;
                     }                
                    
                    return 1;
                }
            });
                                                
            for(int i = 0; i < nums.size(); ++i){
                s.add(new Pair(i,nums.get(i).size() - 1));
            }                                  
            
            int range = Integer.MAX_VALUE;
            int[] r = new int[2];
            
            while(true){
                
                Pair large = s.last();
                s.remove(large);
                
                if(s.isEmpty()){
                    r[0] = r[1] = nums.get(large.i1).get(large.i2);
                    break;
                }
                
                Pair small = s.first();
                int tempRange = nums.get(large.i1).get(large.i2) - nums.get(small.i1).get(small.i2);
                 
                if(range >= tempRange){
                    range = tempRange;
                    r[0] = nums.get(small.i1).get(small.i2);
                    r[1] = nums.get(large.i1).get(large.i2);
                }
                
                if(large.i2 == 0){
                    break;
                }
                
                s.add(new Pair(large.i1,large.i2 - 1));
                
                if(tempRange == 0 && small.i2 != 0){
                    s.remove(small);
                    s.add(new Pair(small.i1,small.i2 - 1));
                }
            }
            
            return r;
        }
    }
    

Log in to reply
 

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