Bird
Raised Fist0
Interview PrepintervalshardGoogleAmazon

Data Stream as Disjoint Intervals

Choose your preparation mode4 modes available
🎯
Data Stream as Disjoint Intervals
hardINTERVALSGoogleAmazon

Imagine you are monitoring a live stream of numbers representing events occurring over time, and you want to continuously summarize these events as a set of non-overlapping intervals.

💡 This problem involves dynamically maintaining a set of disjoint intervals as new numbers arrive. Beginners often struggle because it requires careful interval merging and efficient data structure usage to handle large streams without reprocessing everything.
📋
Problem Statement

Design a data structure that supports adding numbers from a data stream and returning the current set of disjoint intervals covering all added numbers. Implement two methods: addNum(int val) which adds a number to the data structure, and getIntervals() which returns a list of disjoint intervals sorted by their start values.

1 ≤ number of addNum calls ≤ 10^50 ≤ val ≤ 10^4getIntervals will be called multiple times after addNum calls
💡
Example
Input"addNum(1), getIntervals(), addNum(3), getIntervals(), addNum(7), getIntervals(), addNum(2), getIntervals(), addNum(6), getIntervals()"
Output[[1,1]], [[1,1],[3,3]], [[1,1],[3,3],[7,7]], [[1,3],[7,7]], [[1,3],[6,7]]

After adding 1, intervals are [[1,1]]. Adding 3 adds a new interval [[3,3]]. Adding 7 adds [[7,7]]. Adding 2 merges [1,1] and [3,3] into [1,3]. Adding 6 merges [6,6] and [7,7] into [6,7].

  • Adding the same number multiple times → intervals remain unchanged
  • Adding numbers that fill gaps between intervals → intervals merge
  • Adding numbers smaller than all existing intervals → new interval at start
  • Adding numbers larger than all existing intervals → new interval at end
⚠️
Common Mistakes
Not checking if val is already covered before inserting

Duplicate intervals or incorrect merges causing wrong output

✅ Add checks to skip insertion if val lies inside an existing interval

Merging intervals incorrectly by not updating both start and end properly

Intervals overlap or gaps remain, failing correctness

✅ Carefully merge intervals by updating start and end boundaries and removing old intervals

Using a list without sorting or binary search for insertion

Slow insertions and getIntervals calls, leading to TLE

✅ Use balanced tree or binary search to maintain sorted intervals for efficient operations

Not handling edge cases like adding numbers smaller or larger than all intervals

Intervals become unsorted or incorrect

✅ Always check neighbors and insert at correct position maintaining sorted order

🧠
Brute Force (Rebuild Intervals After Each Insert)
💡 This approach exists to build intuition by directly simulating the problem without optimization. It helps understand the core merging logic but is inefficient for large inputs.

Intuition

Store all added numbers in a list, sort them, and then merge consecutive numbers into intervals each time getIntervals is called.

Algorithm

  1. Maintain a list of all added numbers.
  2. On getIntervals, sort the list.
  3. Iterate through sorted numbers, merging consecutive numbers into intervals.
  4. Return the merged intervals.
💡 The main challenge is realizing that sorting and merging after every insertion is straightforward but costly.
</>
Code
class SummaryRanges:
    def __init__(self):
        self.nums = []

    def addNum(self, val: int) -> None:
        self.nums.append(val)

    def getIntervals(self) -> list:
        if not self.nums:
            return []
        sorted_nums = sorted(set(self.nums))
        intervals = []
        start = sorted_nums[0]
        end = sorted_nums[0]
        for num in sorted_nums[1:]:
            if num == end + 1:
                end = num
            else:
                intervals.append([start, end])
                start = num
                end = num
        intervals.append([start, end])
        return intervals

# Example usage:
# obj = SummaryRanges()
# obj.addNum(1)
# print(obj.getIntervals())  # [[1,1]]
# obj.addNum(3)
# print(obj.getIntervals())  # [[1,1],[3,3]]
Line Notes
self.nums = []Initialize list to store all numbers added so far
self.nums.append(val)Add new number to the list without any checks
sorted_nums = sorted(set(self.nums))Sort and remove duplicates before merging intervals
if num == end + 1Check if current number extends the current interval
import java.util.*;

class SummaryRanges {
    private List<Integer> nums;

    public SummaryRanges() {
        nums = new ArrayList<>();
    }

    public void addNum(int val) {
        nums.add(val);
    }

    public int[][] getIntervals() {
        if (nums.isEmpty()) return new int[0][0];
        TreeSet<Integer> set = new TreeSet<>(nums);
        List<int[]> intervals = new ArrayList<>();
        Iterator<Integer> it = set.iterator();
        int start = it.next();
        int end = start;
        while (it.hasNext()) {
            int num = it.next();
            if (num == end + 1) {
                end = num;
            } else {
                intervals.add(new int[]{start, end});
                start = num;
                end = num;
            }
        }
        intervals.add(new int[]{start, end});
        return intervals.toArray(new int[intervals.size()][]);
    }

    // Example main method
    public static void main(String[] args) {
        SummaryRanges obj = new SummaryRanges();
        obj.addNum(1);
        System.out.println(Arrays.deepToString(obj.getIntervals())); // [[1,1]]
        obj.addNum(3);
        System.out.println(Arrays.deepToString(obj.getIntervals())); // [[1,1],[3,3]]
    }
}
Line Notes
nums = new ArrayList<>()Initialize list to store all numbers
nums.add(val)Add new number without validation or merging
TreeSet<Integer> set = new TreeSet<>(nums)Sort and remove duplicates using TreeSet
if (num == end + 1)Check if current number extends the current interval
#include <iostream>
#include <vector>
#include <set>

using namespace std;

class SummaryRanges {
    vector<int> nums;
public:
    SummaryRanges() {}

    void addNum(int val) {
        nums.push_back(val);
    }

    vector<vector<int>> getIntervals() {
        if (nums.empty()) return {};
        set<int> s(nums.begin(), nums.end());
        vector<vector<int>> intervals;
        auto it = s.begin();
        int start = *it;
        int end = *it;
        ++it;
        for (; it != s.end(); ++it) {
            if (*it == end + 1) {
                end = *it;
            } else {
                intervals.push_back({start, end});
                start = *it;
                end = *it;
            }
        }
        intervals.push_back({start, end});
        return intervals;
    }
};

// Example usage
// int main() {
//     SummaryRanges obj;
//     obj.addNum(1);
//     auto intervals = obj.getIntervals();
//     for (auto &iv : intervals) cout << '[' << iv[0] << ',' << iv[1] << ']';
//     cout << '\n';
//     obj.addNum(3);
//     intervals = obj.getIntervals();
//     for (auto &iv : intervals) cout << '[' << iv[0] << ',' << iv[1] << ']';
//     cout << '\n';
//     return 0;
// }
Line Notes
vector<int> nums;Store all numbers added so far
nums.push_back(val);Add new number without merging
set<int> s(nums.begin(), nums.end());Sort and remove duplicates using set
if (*it == end + 1)Check if current number extends the current interval
class SummaryRanges {
    constructor() {
        this.nums = [];
    }

    addNum(val) {
        this.nums.push(val);
    }

    getIntervals() {
        if (this.nums.length === 0) return [];
        const sortedNums = Array.from(new Set(this.nums)).sort((a, b) => a - b);
        const intervals = [];
        let start = sortedNums[0];
        let end = sortedNums[0];
        for (let i = 1; i < sortedNums.length; i++) {
            if (sortedNums[i] === end + 1) {
                end = sortedNums[i];
            } else {
                intervals.push([start, end]);
                start = sortedNums[i];
                end = sortedNums[i];
            }
        }
        intervals.push([start, end]);
        return intervals;
    }
}

// Example usage:
// const obj = new SummaryRanges();
// obj.addNum(1);
// console.log(obj.getIntervals()); // [[1,1]]
// obj.addNum(3);
// console.log(obj.getIntervals()); // [[1,1],[3,3]]
Line Notes
this.nums = []Initialize array to store all numbers
this.nums.push(val)Add new number without merging
Array.from(new Set(this.nums)).sort(...)Remove duplicates and sort before merging
if (sortedNums[i] === end + 1)Check if current number extends the current interval
⏱
Complexity
TimeO(n log n) per getIntervals call due to sorting
SpaceO(n) to store all numbers

Each getIntervals call sorts all numbers seen so far, which is expensive for large n.

💡 For n=100000, sorting each time would be about 100000*log(100000) ≈ 1.5 million operations, which is too slow for real-time.
Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large data streams but helps understand the problem and merging logic.

🧠
Balanced Tree / Sorted Container with Merge on Insert
💡 This approach introduces a balanced tree or sorted container to maintain intervals dynamically, avoiding full re-sorting each time. It teaches efficient data structure usage for interval merging.

Intuition

Keep intervals sorted by start, and on adding a number, find where it fits, then merge with adjacent intervals if overlapping or contiguous.

Algorithm

  1. Maintain a balanced tree (e.g., TreeMap or SortedDict) keyed by interval start.
  2. On addNum(val), find intervals that might overlap or be adjacent to val.
  3. Merge val with these intervals or create a new interval if no overlap.
  4. Update the tree with the merged interval.
💡 The key insight is to only check intervals adjacent to val, not all intervals, to keep operations efficient.
</>
Code
from bisect import bisect_left

class SummaryRanges:
    def __init__(self):
        self.intervals = []  # list of [start, end]

    def addNum(self, val: int) -> None:
        intervals = self.intervals
        if not intervals:
            intervals.append([val, val])
            return
        # Find position to insert
        i = bisect_left(intervals, [val, val])
        # Check left interval
        left_merge = (i > 0 and intervals[i-1][1] + 1 >= val)
        # Check right interval
        right_merge = (i < len(intervals) and intervals[i][0] - 1 <= val) if i < len(intervals) else False

        if left_merge and right_merge:
            # Merge left and right intervals with val
            intervals[i-1][1] = intervals[i][1]
            intervals.pop(i)
        elif left_merge:
            # Extend left interval
            intervals[i-1][1] = max(intervals[i-1][1], val)
        elif right_merge:
            # Extend right interval
            intervals[i][0] = min(intervals[i][0], val)
        else:
            # Insert new interval
            intervals.insert(i, [val, val])

    def getIntervals(self) -> list:
        return self.intervals

# Example usage:
# obj = SummaryRanges()
# obj.addNum(1)
# print(obj.getIntervals())  # [[1,1]]
# obj.addNum(3)
# print(obj.getIntervals())  # [[1,1],[3,3]]
Line Notes
self.intervals = []Store intervals sorted by start
i = bisect_left(intervals, [val, val])Find insertion point for val
left_merge = (i > 0 and intervals[i-1][1] + 1 >= val)Check if val merges with left interval
intervals.insert(i, [val, val])Insert new interval if no merges
import java.util.*;

class SummaryRanges {
    private TreeMap<Integer, Integer> intervals;

    public SummaryRanges() {
        intervals = new TreeMap<>();
    }

    public void addNum(int val) {
        if (intervals.containsKey(val)) return;
        Integer lowerKey = intervals.floorKey(val);
        Integer higherKey = intervals.ceilingKey(val);

        if (lowerKey != null && intervals.get(lowerKey) >= val) {
            return; // val already covered
        }

        boolean leftMerge = false, rightMerge = false;
        if (lowerKey != null && intervals.get(lowerKey) + 1 >= val) {
            leftMerge = true;
        }
        if (higherKey != null && higherKey - 1 <= val) {
            rightMerge = true;
        }

        if (leftMerge && rightMerge) {
            intervals.put(lowerKey, intervals.get(higherKey));
            intervals.remove(higherKey);
        } else if (leftMerge) {
            intervals.put(lowerKey, Math.max(intervals.get(lowerKey), val));
        } else if (rightMerge) {
            int end = intervals.get(higherKey);
            intervals.remove(higherKey);
            intervals.put(val, end);
        } else {
            intervals.put(val, val);
        }
    }

    public int[][] getIntervals() {
        int[][] res = new int[intervals.size()][2];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : intervals.entrySet()) {
            res[i][0] = entry.getKey();
            res[i][1] = entry.getValue();
            i++;
        }
        return res;
    }

    // Example main method
    public static void main(String[] args) {
        SummaryRanges obj = new SummaryRanges();
        obj.addNum(1);
        System.out.println(Arrays.deepToString(obj.getIntervals())); // [[1,1]]
        obj.addNum(3);
        System.out.println(Arrays.deepToString(obj.getIntervals())); // [[1,1],[3,3]]
    }
}
Line Notes
intervals = new TreeMap<>()Use TreeMap to keep intervals sorted by start
Integer lowerKey = intervals.floorKey(val)Find interval start <= val
if (leftMerge && rightMerge)Merge left and right intervals if val bridges them
intervals.put(val, val)Insert new interval if no merge possible
#include <iostream>
#include <map>
#include <vector>

using namespace std;

class SummaryRanges {
    map<int, int> intervals; // key=start, value=end
public:
    SummaryRanges() {}

    void addNum(int val) {
        if (intervals.empty()) {
            intervals[val] = val;
            return;
        }
        auto it = intervals.upper_bound(val);
        int start = val, end = val;

        if (it != intervals.begin()) {
            auto prev = prev(it);
            if (prev->second >= val) return; // already covered
            if (prev->second + 1 == val) {
                start = prev->first;
                intervals.erase(prev);
            }
        }

        if (it != intervals.end() && it->first - 1 == val) {
            end = it->second;
            intervals.erase(it);
        }

        intervals[start] = end;
    }

    vector<vector<int>> getIntervals() {
        vector<vector<int>> res;
        for (auto &p : intervals) {
            res.push_back({p.first, p.second});
        }
        return res;
    }
};

// Example usage
// int main() {
//     SummaryRanges obj;
//     obj.addNum(1);
//     auto intervals = obj.getIntervals();
//     for (auto &iv : intervals) cout << '[' << iv[0] << ',' << iv[1] << ']';
//     cout << '\n';
//     obj.addNum(3);
//     intervals = obj.getIntervals();
//     for (auto &iv : intervals) cout << '[' << iv[0] << ',' << iv[1] << ']';
//     cout << '\n';
//     return 0;
// }
Line Notes
map<int, int> intervals;Store intervals sorted by start using map
auto it = intervals.upper_bound(val);Find first interval with start > val
if (prev->second + 1 == val)Check if val extends previous interval
intervals[start] = end;Insert or update merged interval
class SummaryRanges {
    constructor() {
        this.intervals = new Map(); // key=start, value=end
    }

    addNum(val) {
        if (this.intervals.size === 0) {
            this.intervals.set(val, val);
            return;
        }
        const keys = Array.from(this.intervals.keys()).sort((a,b) => a-b);
        let left = 0, right = keys.length - 1;
        let pos = keys.length;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (keys[mid] > val) {
                pos = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        let start = val, end = val;
        if (pos > 0) {
            const prevStart = keys[pos - 1];
            const prevEnd = this.intervals.get(prevStart);
            if (prevEnd >= val) return; // already covered
            if (prevEnd + 1 >= val) {
                start = prevStart;
                end = Math.max(prevEnd, val);
                this.intervals.delete(prevStart);
            }
        }

        if (pos < keys.length) {
            const nextStart = keys[pos];
            if (nextStart - 1 <= val) {
                end = Math.max(end, this.intervals.get(nextStart));
                this.intervals.delete(nextStart);
            }
        }

        this.intervals.set(start, end);
    }

    getIntervals() {
        const res = [];
        const keys = Array.from(this.intervals.keys()).sort((a,b) => a-b);
        for (const k of keys) {
            res.push([k, this.intervals.get(k)]);
        }
        return res;
    }
}

// Example usage:
// const obj = new SummaryRanges();
// obj.addNum(1);
// console.log(obj.getIntervals()); // [[1,1]]
// obj.addNum(3);
// console.log(obj.getIntervals()); // [[1,1],[3,3]]
Line Notes
this.intervals = new Map()Store intervals keyed by start
const keys = Array.from(this.intervals.keys()).sort(...)Get sorted interval starts for binary search
if (prevEnd + 1 >= val)Check if val merges or extends previous interval
this.intervals.set(start, end)Insert or update merged interval
⏱
Complexity
TimeO(log n) per addNum, O(n) per getIntervals
SpaceO(n) to store intervals

Each addNum uses balanced tree operations to find and merge intervals efficiently. getIntervals returns stored intervals in order.

💡 For n=100000, each insertion is about log(100000) ≈ 17 operations, which is efficient for large streams.
Interview Verdict: Accepted / Efficient for large inputs

This approach balances complexity and performance, suitable for interview coding and real use.

🧠
Optimized Balanced Tree with Interval Merging and Duplicate Checks
💡 This approach refines the balanced tree method by adding checks to avoid duplicate inserts and carefully merging intervals, ensuring minimal updates and maximum efficiency.

Intuition

Before inserting, check if val is already covered by existing intervals to avoid unnecessary merges. Merge only adjacent intervals that connect with val.

Algorithm

  1. Use a balanced tree keyed by interval start to store intervals.
  2. On addNum(val), check if val is already covered by an existing interval.
  3. If not covered, find intervals adjacent to val and merge accordingly.
  4. Update the tree with the merged interval or insert a new one.
💡 Avoiding duplicates and merging only necessary intervals reduces overhead and keeps the data structure minimal.
</>
Code
from bisect import bisect_left

class SummaryRanges:
    def __init__(self):
        self.intervals = []

    def addNum(self, val: int) -> None:
        intervals = self.intervals
        if not intervals:
            intervals.append([val, val])
            return
        i = bisect_left(intervals, [val, val])

        # Check if val is already covered
        if i != 0 and intervals[i-1][0] <= val <= intervals[i-1][1]:
            return
        if i != len(intervals) and intervals[i][0] <= val <= intervals[i][1]:
            return

        left_merge = (i > 0 and intervals[i-1][1] + 1 == val)
        right_merge = (i < len(intervals) and intervals[i][0] - 1 == val)

        if left_merge and right_merge:
            intervals[i-1][1] = intervals[i][1]
            intervals.pop(i)
        elif left_merge:
            intervals[i-1][1] = val
        elif right_merge:
            intervals[i][0] = val
        else:
            intervals.insert(i, [val, val])

    def getIntervals(self) -> list:
        return self.intervals

# Example usage:
# obj = SummaryRanges()
# obj.addNum(1)
# print(obj.getIntervals())  # [[1,1]]
# obj.addNum(3)
# print(obj.getIntervals())  # [[1,1],[3,3]]
Line Notes
if i != 0 and intervals[i-1][0] <= val <= intervals[i-1][1]Check if val is inside left interval to avoid duplicates
if i != len(intervals) and intervals[i][0] <= val <= intervals[i][1]Check if val is inside right interval to avoid duplicates
left_merge = (i > 0 and intervals[i-1][1] + 1 == val)Check if val extends left interval by one
intervals[i-1][1] = intervals[i][1]Merge left and right intervals when val bridges them
import java.util.*;

class SummaryRanges {
    private TreeMap<Integer, Integer> intervals;

    public SummaryRanges() {
        intervals = new TreeMap<>();
    }

    public void addNum(int val) {
        if (intervals.containsKey(val)) return;
        Integer lowerKey = intervals.floorKey(val);
        if (lowerKey != null && intervals.get(lowerKey) >= val) return;

        Integer higherKey = intervals.ceilingKey(val);

        boolean leftMerge = false, rightMerge = false;
        if (lowerKey != null && intervals.get(lowerKey) + 1 == val) {
            leftMerge = true;
        }
        if (higherKey != null && higherKey - 1 == val) {
            rightMerge = true;
        }

        if (leftMerge && rightMerge) {
            intervals.put(lowerKey, intervals.get(higherKey));
            intervals.remove(higherKey);
        } else if (leftMerge) {
            intervals.put(lowerKey, Math.max(intervals.get(lowerKey), val));
        } else if (rightMerge) {
            int end = intervals.get(higherKey);
            intervals.remove(higherKey);
            intervals.put(val, end);
        } else {
            intervals.put(val, val);
        }
    }

    public int[][] getIntervals() {
        int[][] res = new int[intervals.size()][2];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : intervals.entrySet()) {
            res[i][0] = entry.getKey();
            res[i][1] = entry.getValue();
            i++;
        }
        return res;
    }

    // Example main method
    public static void main(String[] args) {
        SummaryRanges obj = new SummaryRanges();
        obj.addNum(1);
        System.out.println(Arrays.deepToString(obj.getIntervals())); // [[1,1]]
        obj.addNum(3);
        System.out.println(Arrays.deepToString(obj.getIntervals())); // [[1,1],[3,3]]
    }
}
Line Notes
if (intervals.containsKey(val)) return;Avoid inserting duplicate interval start
if (lowerKey != null && intervals.get(lowerKey) >= val) return;Check if val already covered by left interval
if (leftMerge && rightMerge)Merge intervals bridged by val
intervals.put(val, val);Insert new interval if no merges
#include <iostream>
#include <map>
#include <vector>

using namespace std;

class SummaryRanges {
    map<int, int> intervals;
public:
    SummaryRanges() {}

    void addNum(int val) {
        auto it = intervals.upper_bound(val);
        if (it != intervals.begin()) {
            auto prev = prev(it);
            if (prev->second >= val) return; // val covered
        }
        if (it != intervals.end() && it->first <= val) return; // val covered

        int start = val, end = val;
        if (it != intervals.begin()) {
            auto prev = prev(it);
            if (prev->second + 1 == val) {
                start = prev->first;
                intervals.erase(prev);
            }
        }
        if (it != intervals.end() && it->first - 1 == val) {
            end = it->second;
            intervals.erase(it);
        }
        intervals[start] = end;
    }

    vector<vector<int>> getIntervals() {
        vector<vector<int>> res;
        for (auto &p : intervals) {
            res.push_back({p.first, p.second});
        }
        return res;
    }
};

// Example usage
// int main() {
//     SummaryRanges obj;
//     obj.addNum(1);
//     auto intervals = obj.getIntervals();
//     for (auto &iv : intervals) cout << '[' << iv[0] << ',' << iv[1] << ']';
//     cout << '\n';
//     obj.addNum(3);
//     intervals = obj.getIntervals();
//     for (auto &iv : intervals) cout << '[' << iv[0] << ',' << iv[1] << ']';
//     cout << '\n';
//     return 0;
// }
Line Notes
if (prev->second >= val) return;Skip if val already covered by previous interval
if (it != intervals.end() && it->first <= val) return;Skip if val covered by current interval
if (prev->second + 1 == val)Check if val extends previous interval by one
intervals[start] = end;Insert or update merged interval
class SummaryRanges {
    constructor() {
        this.intervals = new Map();
    }

    addNum(val) {
        const keys = Array.from(this.intervals.keys()).sort((a,b) => a-b);
        let left = 0, right = keys.length - 1;
        let pos = keys.length;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (keys[mid] > val) {
                pos = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        if (pos > 0) {
            const prevStart = keys[pos - 1];
            const prevEnd = this.intervals.get(prevStart);
            if (prevEnd >= val) return; // val covered
            if (prevEnd + 1 == val) {
                this.intervals.delete(prevStart);
                this.intervals.set(prevStart, val);
            }
        }

        if (pos < keys.length) {
            const nextStart = keys[pos];
            if (nextStart <= val) return; // val covered
            if (nextStart - 1 == val) {
                const end = this.intervals.get(nextStart);
                this.intervals.delete(nextStart);
                this.intervals.set(val, end);
            }
        }

        if (!this.intervals.has(val)) {
            this.intervals.set(val, val);
        }
    }

    getIntervals() {
        const res = [];
        const keys = Array.from(this.intervals.keys()).sort((a,b) => a-b);
        for (const k of keys) {
            res.push([k, this.intervals.get(k)]);
        }
        return res;
    }
}

// Example usage:
// const obj = new SummaryRanges();
// obj.addNum(1);
// console.log(obj.getIntervals()); // [[1,1]]
// obj.addNum(3);
// console.log(obj.getIntervals()); // [[1,1],[3,3]]
Line Notes
if (prevEnd >= val) return;Avoid inserting val if already covered by previous interval
if (prevEnd + 1 == val)Extend previous interval if val is adjacent
if (nextStart <= val) return;Avoid inserting val if covered by next interval
this.intervals.set(val, val);Insert new interval if no merges
⏱
Complexity
TimeO(log n) per addNum, O(n) per getIntervals
SpaceO(n) to store intervals

Duplicate checks prevent unnecessary merges, improving performance slightly over previous approach.

💡 This is the most efficient approach for large data streams, balancing correctness and speed.
Interview Verdict: Accepted / Optimal solution

This approach is recommended for interviews and production due to its efficiency and clarity.

📊
All Approaches - One-Glance Tradeoffs
💡 In interviews, coding the balanced tree approach with merging is recommended for efficiency and clarity.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(n log n) per getIntervalsO(n)NoN/AMention only - never code
2. Balanced Tree with Merge on InsertO(log n) per addNum, O(n) per getIntervalsO(n)NoYesCode this approach in interviews
3. Optimized Balanced Tree with Duplicate ChecksO(log n) per addNum, O(n) per getIntervalsO(n)NoYesPreferred optimal solution to code
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and input/output format.Step 2: Describe the brute force approach to show understanding.Step 3: Explain inefficiencies and introduce balanced tree approach.Step 4: Present optimized balanced tree with duplicate checks.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of interval merging, data structure choice, edge case handling, and code optimization.

Common Follow-ups

  • How to handle very large ranges efficiently → Use segment trees or interval trees
  • Can you support removing numbers? → Requires more complex data structures
💡 These follow-ups test your ability to extend the solution and handle dynamic updates beyond insertion.
🔍
Pattern Recognition

When to Use

1) You need to maintain intervals dynamically; 2) New elements arrive one at a time; 3) Intervals must be disjoint and sorted; 4) Efficient insertion and merging is required.

Signature Phrases

addNumgetIntervalsdisjoint intervalsmerge intervals on insert

NOT This Pattern When

Problems that require interval scheduling or maximum overlap counting are different patterns.

Similar Problems

Merge Intervals - merging overlapping intervals after sortingInsert Interval - inserting and merging a single intervalSummary Ranges - summarizing consecutive numbers as intervals

Practice

(1/5)
1. Consider the following Python function that finds the minimum number of arrows to burst balloons represented as intervals. Given the input points = [[10,16],[2,8],[1,6],[7,12]], what is the value of arrows after processing all intervals?
easy
A. 1
B. 4
C. 3
D. 2

Solution

  1. Step 1: Sort intervals by end coordinate

    Sorted points: [[1,6],[2,8],[7,12],[10,16]]
  2. Step 2: Iterate and count arrows

    Start with arrow_pos=6, arrows=1. Next interval start=2 ≤ 6 (covered), next start=7 > 6 (new arrow), arrows=2, arrow_pos=12. Next start=10 ≤ 12 (covered).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Two arrows suffice to burst all balloons [OK]
Hint: Sort by end, count arrows when start > current arrow position [OK]
Common Mistakes:
  • Not sorting intervals before processing
  • Using start >= arrow_pos instead of start > arrow_pos
  • Off-by-one errors in counting arrows
2. You are given a list of intervals and need to remove all intervals that are covered by another interval. Which approach guarantees an optimal solution with O(n log n) time complexity and O(1) extra space besides the input?
easy
A. Use a brute force nested loop to check coverage between every pair of intervals.
B. Sort intervals by start ascending and end descending, then scan once to count uncovered intervals.
C. Use dynamic programming to find the maximum set of non-covered intervals.
D. Sort intervals by end ascending and greedily pick intervals that do not overlap.

Solution

  1. Step 1: Understand sorting criteria

    Sorting intervals by start ascending and end descending ensures intervals with the same start are ordered from longest to shortest, so coverage can be detected in one pass.
  2. Step 2: Single pass coverage check

    By scanning intervals in sorted order and tracking the maximum end seen, we can count intervals that are not covered by any previous interval.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sorting by start ascending and end descending enables O(n log n) sorting plus O(n) scanning [OK]
Hint: Sort by start asc, end desc, then scan once [OK]
Common Mistakes:
  • Sorting only by start ascending misses coverage when starts equal
  • Using nested loops causes TLE on large inputs
3. Examine the following buggy code for Employee Free Time. Which line contains the subtle bug causing incorrect free time intervals?
medium
A. Line appending end event with (interval[1], -1)
B. Line appending start event with (interval[0], 1)
C. Line updating prev = time inside loop
D. Line sorting events with key=lambda x: (x[0], -x[1])

Solution

  1. Step 1: Understand sorting order impact

    End events must come before start events at same time to avoid false free intervals.
  2. Step 2: Identify bug in sorting key

    Sorting with key (x[0], -x[1]) puts start events before end events at ties, causing incorrect free time detection.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Correct sorting is (x[0], x[1]) to put end events before start [OK]
Hint: End events must sort before start events at same time [OK]
Common Mistakes:
  • Sorting start before end events at same timestamp
4. What is the time complexity of the optimal algorithm that determines if a person can attend all meetings given n intervals, where the algorithm sorts intervals by start time and then checks for overlaps in a single pass?
medium
A. O(n) because we only scan the intervals once after sorting
B. O(n^2) because each interval is compared with all others for overlaps
C. O(n log n) due to sorting the intervals by start time
D. O(log n) because sorting can be done in logarithmic time

Solution

  1. Step 1: Identify sorting cost

    Sorting n intervals by start time takes O(n log n) time.
  2. Step 2: Identify overlap check cost

    Single pass to check overlaps is O(n), which is dominated by sorting.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sorting dominates total time complexity [OK]
Hint: Sorting dominates complexity -> O(n log n) [OK]
Common Mistakes:
  • Confusing single pass check as O(n log n)
  • Assuming nested loops cause O(n^2) here
5. Suppose intervals can be reused multiple times (i.e., you can select the same interval multiple times if it does not overlap with itself). Which modification to the greedy algorithm is correct to find the maximum number of non-overlapping intervals under this new condition?
hard
A. Sort intervals by end time and greedily select intervals, resetting last_end after each selection to allow reuse.
B. Use dynamic programming to consider multiple selections of intervals, since greedy no longer works.
C. Sort intervals by start time and greedily select intervals without updating last_end to allow reuse.
D. Sort intervals by end time and greedily select intervals, but allow intervals to be selected multiple times by not updating last_end.

Solution

  1. Step 1: Understand reuse changes problem

    Allowing reuse means intervals can be selected multiple times, breaking the greedy assumption of one-time selection.
  2. Step 2: Identify correct approach

    Dynamic programming is needed to explore multiple selections and ensure maximum count without overlap.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Greedy fails with reuse; DP handles multiple selections [OK]
Hint: Reuse breaks greedy; DP needed for multiple selections [OK]
Common Mistakes:
  • Trying to reuse intervals by resetting last_end incorrectly
  • Ignoring overlap constraints when reusing intervals
  • Assuming greedy still works unchanged
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard