Leetcode Data Stream as Disjoint Intervals problem solution

YASH PAL,

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].
Leetcode Data Stream as Disjoint Intervals problem solution

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;
        else set.add(val);
        
        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));
            res.add(inter);
        }
        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) {
        addNumHelper(val, rt);
    }
    
    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)
        {
            addNumHelper(val, root->left);
        }else
        {
            addNumHelper(val, root->right);
        }
    }
    
    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);
    }
};

coding problems