Accepted easy solution with DSU(disjoint unions), 400ms


  • 0
    Z

    public class SummaryRanges {

    int [] p;
    public SummaryRanges() {
            p = new int[10000];
            Arrays.fill(p, -1);
    }
    
    public int dsuJoin(int ind){
        if(p[ind] == ind){
            if(ind+1<p.length && p[ind+1] != -1){
                p[ind] = dsuJoin(p[ind+1]);
            }    
        } else {
            p[ind] = dsuJoin(p[ind]);
        }
        return p[ind];
    }
    
    public void addNum(int val) {
        p[val] = val;
        int i = 0;
        while(i<p.length){
            if(p[i] == -1) {
                i++;
            }  else {
                dsuJoin(i);
                i = p[i]+1;
            }
        }
    }
    
    public List<Interval> getIntervals() {
        List<Interval> res = new ArrayList<>();
        int i = 0;
        while(i<p.length){
            if(p[i] == -1){
              i++;
              continue;
            } 
            Interval interval = new Interval(i,p[i]);
            res.add(interval);
            i = p[i]+1;
        }
        return res;
    }
    

    }


Log in to reply
 

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