O(N) join solution using map only....211ms


  • 0
    I

    public class SummaryRanges {
    public class Intervalz {
    Interval i;

        public Intervalz (int val) {
            i = new Interval(val, val);
        }
        
        public boolean isInRange (int val) {
            return val >= i.start - 1 && val <= i.end + 1;
        }
        
        public boolean addNum (int val) {
            if (isInRange (val)) {
                if (i.start > val) {
                    i.start = val;
                    return true;
                } else if (i.end < val) {
                    i.end = val;
                    return true;
                }
            } 
            return false;
        }
        
        public void joinIntervalz(Intervalz t) {
            i.end = t.i.end;
        }
    }
    
    Map<Integer, Intervalz> map;
    Set<Interval> set;
    /** Initialize your data structure here. */
    public SummaryRanges() {
        map = new HashMap<>();
        set = new HashSet<>();
    }
    
    public void addNum(int val) {
        int lower = val - 1;
        int higher = val + 1;
        Intervalz curr;
        if (map.containsKey(val)) return;
        else if(map.containsKey(lower) && map.containsKey(higher)) {
            curr = map.get(lower);
            Intervalz r = map.get(higher);
            curr.joinIntervalz(r);
            for (int i = r.i.start; i <= r.i.end; i++) {
                map.put(i, curr);
            }
            set.remove(r.i);
        }
        else if (map.containsKey(lower)) {
            curr = map.get(lower);
        } else if (map.containsKey(higher)) {
            curr = map.get(higher);
        }
        else {
            curr = new Intervalz(val);
            set.add(curr.i);
        }
        curr.addNum(val);
        map.put(val, curr);
    }
    
    public List<Interval> getIntervals() {
        List<Interval> res = new ArrayList<>();
        for (Interval i : set) res.add(i);
        Collections.sort(res, new Comparator<Interval>() {
           @Override
           public int compare (Interval i1, Interval i2) {
               return i1.start - i2.start;
           }
        });
        return res;
    }
    

    }


Log in to reply
 

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