Simple Java solution with ArrayList and HashSet, O(1) per adding. O(nlogn) per merging. Beats 97%.


  • 0
    S

    public class SummaryRanges {

    /** Initialize your data structure here. */
    List<Interval> list;
    Set<Integer> sets;
    public SummaryRanges() {
        list = new ArrayList<>();
        sets = new HashSet<>();
    }
    //O(1)
    public void addNum(int val) {
        if(!sets.contains(val)){
            Interval itvl = new Interval(val, val);
            list.add(itvl);
            sets.add(val);
        }
    }
    //O(nlogn)
    public List<Interval> getIntervals() {
        
        List<Interval> ans = new ArrayList<Interval>();
        Collections.sort(list, new Comparator<Interval>(){
            public int compare(Interval l1, Interval l2){
                return l1.start - l2.start;
            } 
        });
        int curStart = list.get(0).start;
        int curEnd = list.get(0).end;
        
        for(int i=1; i<list.size(); i++){
            if(list.get(i).start == curEnd+1){
                curEnd = list.get(i).end;
            }else{
                ans.add(new Interval(curStart, curEnd));
                curStart = list.get(i).start;
                curEnd = list.get(i).end;
            }
        }
        
        ans.add(new Interval(curStart, curEnd));
        
        list = ans;
        
        return ans;
    }
    

    }

    Correct me if I'm wrong somewhere. :)


Log in to reply
 

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