Sponsored
Sponsored
In this approach, maintain a sorted array of intervals and merge them appropriately as new numbers are added. When adding a new number, iterate through the intervals to find the potential merging points and update the intervals accordingly.
Time Complexity: O(N), where N is the number of intervals (after all numbers are added).
Space Complexity: O(N)
1class SummaryRanges {
2 constructor() {
3 this.intervals = [];
4 }
5
6 addNum(value) {
7 for (let interval of this.intervals) {
8 if (interval[0] <= value && value <= interval[1]) {
9 return;
10 }
11 if (interval[0] === value + 1) {
12 interval[0] = value;
13 this.merge();
14 return;
15 }
16 if (interval[1] === value - 1) {
17 interval[1] = value;
18 this.merge();
19 return;
20 }
21 }
22 this.intervals.push([value, value]);
23 this.intervals.sort((a, b) => a[0] - b[0]);
24 }
25
26 getIntervals() {
27 return this.intervals;
28 }
29
30 merge() {
31 let merged = [];
32 for (let interval of this.intervals) {
33 if (merged.length === 0 || merged[merged.length - 1][1] < interval[0] - 1) {
34 merged.push(interval);
35 } else {
36 merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
37 }
38 }
39 this.intervals = merged;
40 }
41}This JavaScript solution uses similar logic to the Python version, maintaining a sorted list of intervals that gets updated based on new numbers added.
This approach uses a data structure like TreeMap in Java or SortedDict in Python to maintain the intervals in sorted order. This provides efficient query and update operations which is essential for managing intervals dynamically.
Time Complexity: O(log N) for add, where N is the number of intervals.
Space Complexity: O(N)
1import java.util.TreeMap;
2
3
The Java solution uses a TreeMap to efficiently maintain and update intervals. Each time a number is added, it checks for possible merges with adjacent intervals and updates the map accordingly.