Neat O(N) Java solution


  • 0
    T

    Of coz using binary search could reduce the time complexity from O(N) to O(logN). However, the O(N) solution has clear logic and is easy to understand

    public class SummaryRanges {
        private List<Integer> bottom;
        private List<Integer> top;
    
        /** Initialize your data structure here. */
        public SummaryRanges() {
            bottom=new ArrayList<Integer>();
            top=new ArrayList<Integer>();
        }
        
        public void addNum(int val) {
            if(bottom.size()==0){
                bottom.add(val);
                top.add(val);
                return;
            }
            //val is larger than or equal to the start of the last interval
            if(val==bottom.get(bottom.size()-1)) return;
            if(val>bottom.get(bottom.size()-1)){
                if(val<=top.get(bottom.size()-1)) return;
                if(val-top.get(bottom.size()-1)==1){
                    top.set(bottom.size()-1,val);
                    return;
                }
                bottom.add(val);
                top.add(val);
            }
            //val is smaller than or equal to the start of the first interval
            if(val==bottom.get(0)) return;
            if(val<bottom.get(0)){
                if(bottom.get(0)-1==val){
                    bottom.set(0,val);
                    return;
                }
                bottom.add(0,val);
                top.add(0,val);
            }
            //val is in between
            int i=0;//position of val
            while(bottom.get(i)<val){
                i++;
            }
            if(bottom.get(i)==val||top.get(i-1)>=val) return;
            if(bottom.get(i)-1==val&&top.get(i-1)+1==val){
                bottom.remove(i);
                top.remove(i-1);
                return;
            }
            if(bottom.get(i)-1==val){
                bottom.set(i,val);
                return;
            }
            if(top.get(i-1)+1==val){
                top.set(i-1,val);
                return;
            }
            bottom.add(i,val);
            top.add(i,val);
        }
        
        public List<Interval> getIntervals() {
            List<Interval> res=new ArrayList();
            for(int i=0;i<bottom.size();i++){
                res.add(new Interval(bottom.get(i),top.get(i)));
            }
            return res;
        }
    }

  • 0
    B

    It is actually O(N²): for each new element in the stream, you iterate through what is already in you list (possible N elements)


Log in to reply
 

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