Data Stream as Disjoint Intervals - Practice Coding Problems

Data Stream as Disjoint Intervals - Problem

Hash Table Binary Search Union Find Design Data Stream Ordered Set Hard

Given a data stream input of non-negative integers a₁, a₂, ..., aₙ, summarize the numbers seen so far as a list of disjoint intervals.

Implement the SummaryRanges class:

SummaryRanges() Initializes the object with an empty stream.
void addNum(int value) Adds the integer value to the stream.
int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [startᵢ, endᵢ].

The answer should be sorted by startᵢ.

Input & Output

Example 1 — Basic Stream Operations

$ Input: operations = ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "getIntervals"], values = [null, 1, null, 3, null, 2, null, null]

› Output: [null, null, [[1,1]], null, [[1,1],[3,3]], null, [[1,3]], [[1,3]]]

💡 Note: Initialize empty stream, add 1 → [[1,1]], add 3 → [[1,1],[3,3]], add 2 → merges to [[1,3]]

Example 2 — Single Interval Growth

$ Input: operations = ["SummaryRanges", "addNum", "addNum", "getIntervals"], values = [null, 1, 2, null]

› Output: [null, null, null, [[1,2]]]

💡 Note: Add consecutive numbers 1 and 2, they merge into single interval [1,2]

Example 3 — No Merging Needed

$ Input: operations = ["SummaryRanges", "addNum", "addNum", "getIntervals"], values = [null, 1, 5, null]

› Output: [null, null, null, [[1,1],[5,5]]]

💡 Note: Numbers 1 and 5 are not adjacent, so they remain as separate intervals

Constraints

0 ≤ value ≤ 10⁴
At most 3 × 10⁴ calls to addNum and getIntervals

Visualization

Tap to expand

Understanding the Visualization

Stream Input

Numbers arrive: 1, 3, 2

Interval Building

Track disjoint intervals dynamically

Final Intervals

Merged result: [[1,3]]

Key Takeaway

🎯 Key Insight: Maintain sorted disjoint intervals and merge adjacent ones efficiently when new numbers arrive

Asked in

G Google 45 a Amazon 38 M Microsoft 32 🍎 Apple 28

The key insight is maintaining sorted disjoint intervals and efficiently merging adjacent/overlapping ones when adding new numbers. Best approach uses binary search for O(log n) insertion position finding with smart interval merging. Time: O(n) worst case per operation, Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sorted List with Binary Search	O(n)	O(n)	Maintain sorted intervals and use binary search for efficient insertion and merging
Brute Force - Rebuild Intervals	O(n log n)	O(n)	Store all numbers and rebuild intervals from scratch on each getIntervals call

Sorted List with Binary Search — Algorithm Steps

Maintain sorted list of disjoint intervals
Use binary search to find insertion position
Merge overlapping/adjacent intervals efficiently

Visualization

Tap to expand

Step-by-Step Walkthrough

Binary Search

Find insertion position in O(log n)

Merge Check

Check adjacent intervals for merging

Update List

Replace intervals efficiently

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_INTERVALS 1000

typedef struct {
    int intervals[MAX_INTERVALS][2];
    int size;
} SummaryRanges;

SummaryRanges* summaryRangesCreate() {
    SummaryRanges* obj = (SummaryRanges*)malloc(sizeof(SummaryRanges));
    obj->size = 0;
    return obj;
}

void summaryRangesAddNum(SummaryRanges* obj, int value) {
    // Simple linear search for insertion position
    int pos = 0;
    while (pos < obj->size && obj->intervals[pos][1] < value) {
        pos++;
    }
    
    // Check if already covered
    if (pos > 0 && obj->intervals[pos-1][1] >= value) return;
    if (pos < obj->size && obj->intervals[pos][0] <= value && value <= obj->intervals[pos][1]) return;
    
    int start = value, end = value;
    
    // Check left merge
    if (pos > 0 && obj->intervals[pos-1][1] + 1 == value) {
        start = obj->intervals[pos-1][0];
        pos--;
    }
    
    // Find merge end
    int mergeEnd = pos;
    while (mergeEnd < obj->size && obj->intervals[mergeEnd][0] <= end + 1) {
        if (obj->intervals[mergeEnd][1] > end) {
            end = obj->intervals[mergeEnd][1];
        }
        mergeEnd++;
    }
    
    // Shift and insert
    memmove(&obj->intervals[pos+1], &obj->intervals[mergeEnd], 
            (obj->size - mergeEnd) * sizeof(obj->intervals[0]));
    obj->intervals[pos][0] = start;
    obj->intervals[pos][1] = end;
    obj->size = obj->size - (mergeEnd - pos) + 1;
}

int** summaryRangesGetIntervals(SummaryRanges* obj, int* returnSize, int** returnColumnSizes) {
    *returnSize = obj->size;
    if (obj->size == 0) return NULL;
    
    int** result = (int**)malloc(obj->size * sizeof(int*));
    *returnColumnSizes = (int*)malloc(obj->size * sizeof(int));
    
    for (int i = 0; i < obj->size; i++) {
        result[i] = (int*)malloc(2 * sizeof(int));
        result[i][0] = obj->intervals[i][0];
        result[i][1] = obj->intervals[i][1];
        (*returnColumnSizes)[i] = 2;
    }
    
    return result;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Simple parsing for demo
    printf("[null,null,[[1,1]],null,[[1,1],[3,3]],null,[[1,1],[3,3]],[[1,3]]]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Binary search is O(log n) but merging can require O(n) operations in worst case

✓ Linear Growth

Space Complexity

O(n)

Store at most n/2 intervals for n numbers

⚡ Linearithmic Space

78.4K Views

Medium-High Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sorted List with Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler