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

• 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<>();
}

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);
}
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;
}
``````

}

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