# Leetcode Data Stream as Disjoint Intervals problem solution

In this Leetcode Data Stream as Disjoint Intervals problem solution, you have given a data stream input of non-negative integers a1, a2, ..., an, summarize the numbers seen so far as a list of disjoint intervals.

Implement the SummaryRanges class:

1. SummaryRanges() Initializes the object with an empty stream.
2. void addNum(int val) Adds the integer val to the stream.
3. int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [starti, endi].

## Problem solution in Python.

```class SummaryRanges:

class Number:
def __init__(self, num):
self.num = num

def __init__(self):
"""
Initialize your data structure here.
"""
self.l_range_bounds = {}
self.u_range_bounds = {}
self.nums = {}
self.ranges = {}

def addNum(self, val: int) -> None:
if val in self.nums:
return
self.nums[val] = True
if (val + 1) not in self.l_range_bounds and (val - 1) not in self.u_range_bounds:
self.l_range_bounds[val] = val
self.u_range_bounds[val] = val
self.ranges[val] = [val, val]
if (val + 1) in self.l_range_bounds and (val - 1) in self.u_range_bounds:
l_idx = self.l_range_bounds[val + 1]
u_idx = self.u_range_bounds[val - 1]
l_higher = self.ranges[l_idx][1]
self.ranges[u_idx][1] = l_higher
self.u_range_bounds[l_higher] = u_idx
del self.ranges[l_idx]
del self.l_range_bounds[val + 1]
del self.u_range_bounds[val - 1]
elif (val + 1) in self.l_range_bounds:
idx = self.l_range_bounds[val + 1]
self.l_range_bounds[val] = idx
del self.l_range_bounds[val + 1]
self.ranges[idx][0] = val

elif (val - 1) in self.u_range_bounds:
idx = self.u_range_bounds[val - 1]
self.u_range_bounds[val] = idx
del self.u_range_bounds[val - 1]
self.ranges[idx][1] = val

def getIntervals(self) -> List[List[int]]:
result = list(self.ranges.values())
result.sort(key = lambda x : x[0])
return result
```

## Problem solution in Java.

```class SummaryRanges {

private Map<Integer, Integer> start;
private Map<Integer, Integer> end;
private Set<Integer> set;
/** Initialize your data structure here. */
public SummaryRanges() {
start = new HashMap<>();
end = new HashMap<>();
set = new HashSet<>();
}

public void addNum(int val) {
int m1 = val - 1;
int p1 = val + 1;

if (set.contains(val)) return;

if (start.containsKey(p1) && end.containsKey(m1)) {
int s = end.remove(m1);
int e = start.remove(p1);
start.put(s, e);
end.put(e, s);
} else if (start.containsKey(p1)) {
int e = start.remove(p1);
start.put(val, e);
end.put(e, val);
} else if (end.containsKey(m1)) {
int s = end.remove(m1);
end.put(val, s);
start.put(s, val);
} else {
start.put(val, val);
end.put(val, val);
}
}

public List<Interval> getIntervals() {
List<Interval> res = new ArrayList<>();
for (int i : start.keySet()) {
Interval inter = new Interval(i, start.get(i));
}
Collections.sort(res, (i1, i2) -> i1.start - i2.start);
return res;
}
}
```

## Problem solution in C++.

```struct MMTreeNode
{
Interval range;
MMTreeNode *left;
MMTreeNode *right;
MMTreeNode(int s, int e):range(s, e), left(NULL), right(NULL){}
};
class SummaryRanges {
private:
MMTreeNode *rt;
public:
/** Initialize your data structure here. */
SummaryRanges() {
rt = NULL;
}

void addNum(int val) {
}

void addNumHelper(int val, MMTreeNode *&root)
{
if(root == NULL)
{
root = new MMTreeNode(val, val);
return;
}
if(root->range.start <= val && root->range.end >= val) return;
if(root->range.start == val + 1)
{
root->range.start = val;
//find the rightest node on the left subtree
if(root->left)
{
MMTreeNode *node = root->left;
if(node->right == NULL)
{
//node's right subtree doesn't exist
if(node->range.end == val - 1)
{
root->range.start = node->range.start;
root->left = node->left;
delete node;
}
return;
}
//if right subtree exists, then find the rightest node
MMTreeNode *parent;
while(node->right)
{
parent = node;
node = node->right;
}
if(node->range.end == val - 1)
{
parent->right = node->left;
root->range.start = node->range.start;
delete node;
}
}
return;
}else if(root->range.end == val - 1)
{
root->range.end = val;
//find the leftest node on the right subtree
if(root->right)
{
MMTreeNode *node = root->right;
if(node->left == NULL)
{
//node's left subtree doesn't exist
if(node->range.start == val + 1)
{
root->range.end = node->range.end;
root->right = node->right;
delete node;
}
return;
}
//if left subtree exists, then find the leftest node
MMTreeNode *parent = root;
while(node->left)
{
parent = node;
node = node->left;
}
if(node->range.start == val + 1)
{
parent->left = node->right;
root->range.end = node->range.end;
delete node;
}
}
return;
}else if(root->range.start > val)
{
}else
{
}
}

vector<Interval> getIntervals() {
vector<Interval> result;
getIntervalsHelper(rt, result);
return result;
}
void getIntervalsHelper(MMTreeNode *root, vector<Interval> &result)
{
if(root == NULL) return;
getIntervalsHelper(root->left, result);
result.push_back(root->range);
getIntervalsHelper(root->right, result);
}
};
```