Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

Leetcode Data Stream as Disjoint Intervals problem solution

YASH PAL, 31 July 2024

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

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes