LeetCode //C - 352. Data Stream as Disjoint Intervals

352. Data Stream as Disjoint Intervals

Given a data stream input of non-negative integers $a_1, a_2, ..., a_n$ , 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_i, end_i]$ . The answer should be sorted by $start_i$ .

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]]]
Explanation
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1); // arr = [1]
summaryRanges.getIntervals(); // return [[1, 1]]
summaryRanges.addNum(3); // arr = [1, 3]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
summaryRanges.addNum(7); // arr = [1, 3, 7]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2); // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]

Constraints:

$0 <= value <= 10^4$
At most $3 * 10^4$ calls will be made to addNum and getIntervals.
At most $10^2$ calls will be made to getIntervals.

From: LeetCode
Link: 352. Data Stream as Disjoint Intervals

Solution:

Ideas:

1. Intervals Representation:

Intervals are stored in a 2D array intervals, where each interval is represented as a pair [start, end].
For example, the intervals for numbers [1, 3, 7] would be stored as [[1, 1], [3, 3], [7, 7]].

2. Efficient Insertion:

When a new number is added, the code finds the appropriate place to insert it. The intervals are maintained in sorted order, so the number is compared to the existing intervals.
Depending on whether the new number is adjacent to an existing interval, it either extends or merges the intervals.

3. Merging Logic:

Merge with the previous interval: If the new number is just after the previous interval (i.e., new number == previous interval end + 1), then the previous interval is extended.
Merge with the next interval: If the new number is just before the next interval (i.e., new number == next interval start - 1), then the next interval is extended.
Merge both previous and next intervals: If the new number is adjacent to both the previous and the next intervals, the two intervals are merged into one.
New Interval: If the new number is not adjacent to any existing intervals, a new interval is created.

4. Dynamic Array Management:

The intervals array has an initial capacity, and when it fills up, it is dynamically resized to accommodate more intervals. This ensures that the solution can handle up to the maximum number of intervals allowed by the problem constraints.

Code:

typedef struct {int** intervals;   // To store the intervals as a 2D arrayint size;          // The current number of intervalsint capacity;      // The allocated capacity of the intervals array
} SummaryRanges;SummaryRanges* summaryRangesCreate() {SummaryRanges* obj = (SummaryRanges*)malloc(sizeof(SummaryRanges));obj->size = 0;obj->capacity = 10; // Initial capacityobj->intervals = (int**)malloc(sizeof(int*) * obj->capacity);for (int i = 0; i < obj->capacity; ++i) {obj->intervals[i] = (int*)malloc(sizeof(int) * 2); // Each interval has two elements [start, end]}return obj;
}void summaryRangesAddNum(SummaryRanges* obj, int value) {int i = 0;// Find the position to insert or merge intervalswhile (i < obj->size && obj->intervals[i][1] < value) {i++;}// Check if value is already included in an intervalif (i < obj->size && obj->intervals[i][0] <= value && obj->intervals[i][1] >= value) {return;}// Merge with the previous and next intervals if possibleint mergeWithPrev = (i > 0 && obj->intervals[i - 1][1] + 1 == value);int mergeWithNext = (i < obj->size && obj->intervals[i][0] - 1 == value);if (mergeWithPrev && mergeWithNext) {// Merge both previous and next intervalsobj->intervals[i - 1][1] = obj->intervals[i][1];// Remove the current intervalfor (int j = i; j < obj->size - 1; ++j) {obj->intervals[j][0] = obj->intervals[j + 1][0];obj->intervals[j][1] = obj->intervals[j + 1][1];}obj->size--;} else if (mergeWithPrev) {// Merge with the previous intervalobj->intervals[i - 1][1] = value;} else if (mergeWithNext) {// Merge with the next intervalobj->intervals[i][0] = value;} else {// Insert a new intervalif (obj->size == obj->capacity) {obj->capacity *= 2;obj->intervals = (int**)realloc(obj->intervals, sizeof(int*) * obj->capacity);for (int j = obj->size; j < obj->capacity; ++j) {obj->intervals[j] = (int*)malloc(sizeof(int) * 2);}}for (int j = obj->size; j > i; --j) {obj->intervals[j][0] = obj->intervals[j - 1][0];obj->intervals[j][1] = obj->intervals[j - 1][1];}obj->intervals[i][0] = value;obj->intervals[i][1] = value;obj->size++;}
}int** summaryRangesGetIntervals(SummaryRanges* obj, int* retSize, int** retColSize) {*retSize = obj->size;*retColSize = (int*)malloc(sizeof(int) * obj->size);for (int i = 0; i < obj->size; ++i) {(*retColSize)[i] = 2; // Each interval has two columns}return obj->intervals;
}void summaryRangesFree(SummaryRanges* obj) {for (int i = 0; i < obj->capacity; ++i) {free(obj->intervals[i]);}free(obj->intervals);free(obj);
}/*** Your SummaryRanges struct will be instantiated and called as such:* SummaryRanges* obj = summaryRangesCreate();* summaryRangesAddNum(obj, value);* int** param_2 = summaryRangesGetIntervals(obj, retSize, retColSize);* summaryRangesFree(obj);*/