Practice/Meta/Leetcode 352. Data Stream as Disjoint Intervals

Leetcode 352. Data Stream as Disjoint Intervals

CodingOptional

Problem

You need to design a data structure that tracks integers from a stream and efficiently represents them as a collection of sorted, non-overlapping intervals. The structure must support two operations:

1. addNum(value): Add an integer to the tracker
2. getIntervals(): Return all tracked integers represented as a sorted list of disjoint intervals in the form [start, end] where both endpoints are inclusive

When a new number is added, it should be merged with existing intervals if it's adjacent to or overlaps with them. For example, if you have intervals [1,3] and [6,9], adding 5 would create [1,3], [5,5], [6,9], but adding 4 would merge everything into [1,9].

Requirements

1. Implement a RangeTracker class with an empty constructor
2. Implement addNum(value) that adds an integer to the tracker
3. Implement getIntervals() that returns a sorted list of disjoint intervals
4. Intervals should be returned in ascending order by their start values
5. Adjacent or overlapping intervals must be merged automatically
6. Duplicate values should not create redundant intervals

Constraints

• 0 ≤ value ≤ 10^6
• At most 3 × 10^4 calls will be made to addNum and getIntervals combined
• The intervals returned must be sorted and non-overlapping
• Each interval [start, end] satisfies start ≤ end

Examples

Example 1:

` Operations: ["RangeTracker", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"] Values: [[], [1], [], [3], [], [2], []]

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

Explanation:

• Create tracker
• Add 1 → intervals are [[1,1]]
• Add 3 → intervals are [[1,1],[3,3]]
• Add 2 → fills the gap, intervals merge to [[1,3]] `

Example 2:

` Operations: ["RangeTracker", "addNum", "addNum", "addNum", "getIntervals"] Values: [[], [1], [5], [10], []]

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

Explanation: Three non-adjacent numbers create three separate intervals `

Example 3:

` Operations: ["RangeTracker", "addNum", "addNum", "getIntervals", "addNum", "getIntervals"] Values: [[], [5], [7], [], [6], []]

Output: [null, null, null, [[5,5],[7,7]], null, [[5,7]]]

Explanation: Adding 6 bridges the gap between 5 and 7, merging them into one interval `