352. Data Stream as Disjoint Intervals – Leetcode Solutions

Example 1:

Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

class SummaryRanges:
    def __init__(self):
        # Initialize an empty list to store the intervals
        self.intervals = []
    
    def addNum(self, value: int) -> None:
        # If no intervals exist yet, just add the first interval
        if not self.intervals:
            self.intervals.append([value, value])
            return
        
        # Find the correct position to insert the new value
        new_interval = [value, value]
        merged_intervals = []
        inserted = False
        
        for interval in self.intervals:
            if interval[1] < value - 1:  # Current interval is completely before the new value
                merged_intervals.append(interval)
            elif interval[0] > value + 1:  # Current interval is completely after the new value
                if not inserted:
                    merged_intervals.append(new_interval)
                    inserted = True
                merged_intervals.append(interval)
            else:  # Intervals overlap or are adjacent, we need to merge
                new_interval[0] = min(new_interval[0], interval[0])
                new_interval[1] = max(new_interval[1], interval[1])
        
        # If new_interval wasn't inserted, add it at the end
        if not inserted:
            merged_intervals.append(new_interval)
        
        # Update the intervals with the merged result
        self.intervals = merged_intervals

    def getIntervals(self) -> List[List[int]]:
        # Return the current list of disjoint intervals
        return self.intervals

class SummaryRanges {
private:
    // A set to store the unique numbers in the stream
    set<int> numbers;
    
public:
    // Constructor to initialize the object with an empty stream
    SummaryRanges() {
        // numbers set will hold the integers as they are added
    }

    // Method to add a number to the stream
    void addNum(int value) {
        // We use a set because it automatically handles duplicates and sorts the elements.
        numbers.insert(value);
    }

    // Method to return the summary of intervals
    vector<vector<int>> getIntervals() {
        vector<vector<int>> intervals;

        // If there are no numbers in the stream, return an empty vector
        if (numbers.empty()) return intervals;

        // Variables to track the start and end of the current interval
        int start = -1, end = -1;

        // Iterate through the sorted set of numbers
        for (int num : numbers) {
            if (start == -1) {
                // Initialize the start and end of the first interval
                start = end = num;
            } else if (num == end + 1) {
                // If the current number continues the interval (is consecutive)
                end = num;
            } else {
                // If the current number is not consecutive, store the previous interval
                intervals.push_back({start, end});
                // Start a new interval
                start = end = num;
            }
        }

        // Add the last interval
        intervals.push_back({start, end});

        return intervals;
    }
};

// Constructor for the SummaryRanges class
var SummaryRanges = function() {
    // Initialize an empty array to store the intervals
    this.intervals = [];
};

/** 
 * @param {number} value
 * @return {void}
 */
SummaryRanges.prototype.addNum = function(value) {
    // Edge case: if no intervals exist, simply add the new number as a new interval
    if (this.intervals.length === 0) {
        this.intervals.push([value, value]);
        return;
    }

    // Find the appropriate place to insert the new number
    for (let i = 0; i < this.intervals.length; i++) {
        let [start, end] = this.intervals[i];
        
        // Case 1: The new value is already covered by an existing interval, so no need to add it
        if (value >= start && value <= end) {
            return;
        }

        // Case 2: The new value should extend an existing interval (either on the left or right)
        if (value === end + 1) {
            // Extend the current interval to the right
            this.intervals[i][1] = value;
            
            // Check if the next interval starts where the current interval ends
            if (i + 1 < this.intervals.length && this.intervals[i + 1][0] === value + 1) {
                // Merge the next interval with the current one
                this.intervals[i][1] = this.intervals[i + 1][1];
                this.intervals.splice(i + 1, 1); // Remove the next interval
            }
            return;
        }

        // Case 3: The new value should be inserted between two intervals
        if (value === start - 1) {
            // Extend the current interval to the left
            this.intervals[i][0] = value;
            return;
        }

        // Case 4: The new value lies before the current interval and does not overlap
        if (value < start) {
            // Insert a new interval for the value
            this.intervals.splice(i, 0, [value, value]);
            return;
        }
    }

    // Case 5: If the value is larger than all existing intervals, add it as a new interval at the end
    this.intervals.push([value, value]);
};

/**
 * @return {number[][]}
 */
SummaryRanges.prototype.getIntervals = function() {
    // Simply return the list of intervals
    return this.intervals;
};

public class SummaryRanges {
    // TreeMap to store the start of the interval as the key, and the end of the interval as the value.
    private TreeMap<Integer, Integer> intervals;

    // Constructor to initialize the object with an empty TreeMap.
    public SummaryRanges() {
        intervals = new TreeMap<>();
    }

    // Adds the integer value to the stream and updates the intervals accordingly.
    public void addNum(int value) {
        // Check if the value is already part of an existing interval
        if (intervals.containsKey(value)) {
            return; // The value is already in an interval, so no need to do anything.
        }

        // Find the intervals just before and after the new value
        Integer low = intervals.floorKey(value); // The largest key that is less than or equal to value
        Integer high = intervals.ceilingKey(value); // The smallest key that is greater than or equal to value

        // Case 1: Value is adjacent to an interval on both sides
        if (low != null && intervals.get(low) + 1 == value && high != null && high == value + 1) {
            // Merge the two adjacent intervals into one
            intervals.put(low, intervals.get(high));
            intervals.remove(high); // Remove the right interval since it's merged.
        }
        // Case 2: Value is adjacent only to the left interval
        else if (low != null && intervals.get(low) + 1 >= value) {
            // Extend the left interval to include the value
            intervals.put(low, Math.max(intervals.get(low), value));
        }
        // Case 3: Value is adjacent only to the right interval
        else if (high != null && high == value + 1) {
            // Insert the value as a new start of the interval
            intervals.put(value, intervals.get(high));
            intervals.remove(high); // Remove the right interval since it's merged.
        }
        // Case 4: Value is not adjacent to any interval
        else {
            // Create a new interval just for this value
            intervals.put(value, value);
        }
    }

    // Returns the current list of disjoint intervals.
    public int[][] getIntervals() {
        // Convert the TreeMap's entrySet to an array of intervals
        int[][] result = new int[intervals.size()][2];
        int i = 0;
        for (var entry : intervals.entrySet()) {
            result[i][0] = entry.getKey(); // Start of the interval
            result[i][1] = entry.getValue(); // End of the interval
            i++;
        }
        return result;
    }
}