Data Stream as Disjoint Intervals

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n log n) per getIntervals	O(n)	No	N/A	Mention only - never code
2. Balanced Tree with Merge on Insert	O(log n) per addNum, O(n) per getIntervals	O(n)	No	Yes	Code this approach in interviews
3. Optimized Balanced Tree with Duplicate Checks	O(log n) per addNum, O(n) per getIntervals	O(n)	No	Yes	Preferred 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. You are given a list of trips, each with a number of passengers, a start location, and an end location. You need to determine if a vehicle with a fixed capacity can carry all passengers without exceeding capacity at any point along the route. Which algorithmic approach best guarantees an optimal and efficient solution?

easy

A. Brute force simulation by incrementing passenger count at every location for each trip

B. Greedy algorithm that picks trips with earliest end location first

C. Dynamic programming to find maximum passengers at each location using state transitions

D. Sweep line algorithm that processes passenger count changes at trip start and end points

Solution

1. Step 1: Understand problem constraints

   The problem requires tracking passenger counts over intervals defined by start and end locations.

2. Step 2: Identify suitable algorithm

   Sweep line processes events (passenger changes) in sorted order, efficiently tracking capacity usage without simulating every location.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sweep line handles interval events optimally [OK]

Hint: Intervals with start/end events -> sweep line [OK]

Common Mistakes:

• Assuming greedy earliest end works for capacity constraints
• Thinking DP is needed for counting passengers
• Using brute force for large location ranges

2. Consider the following Python function for interval intersections:

from typing import List

def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    i, j = 0, 0
    result = []
    while i < len(A) and j < len(B):
        if A[i][1] < B[j][0]:
            i += 1
        elif B[j][1] < A[i][0]:
            j += 1
        else:
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            result.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
    return result

A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
print(intervalIntersection(A, B))

What is the final output printed by this code?

easy

A. [[1,2],[5,5],[8,10],[15,23],[24,25],[25,26]]

B. [[1,2],[5,5],[8,10],[15,23],[24,25],[25,25]]

C. [[1,2],[5,5],[8,10],[15,23],[24,24],[25,26]]

D. [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Solution

1. Step 1: Trace first intersection

   Compare [0,2] and [1,5]: overlap is [1,2], add to result.

2. Step 2: Advance pointers and find all intersections

   Following pointer moves and overlaps yield [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches manual step-by-step intersection results [OK]

Hint: Trace pointer increments carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Including intervals beyond intersection
• Merging adjacent but non-overlapping intervals
• Off-by-one in pointer increments

3. Consider the following buggy code for inserting an interval. Which line contains the subtle bug that can cause incorrect output when the input list is empty?

from typing import List

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    intervals.append(newInterval)
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for i in range(1, len(intervals)):
        if intervals[i][0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
        else:
            merged.append(intervals[i])
    return merged

medium

A. Line 5: merged = [intervals[0]]

B. Line 3: intervals.append(newInterval)

C. Line 7: if intervals[i][0] <= merged[-1][1]:

D. Line 9: merged.append(intervals[i])

Solution

1. Step 1: Consider empty intervals input

   If intervals is empty, after appending newInterval, intervals has length 1.

2. Step 2: Check initialization of merged

   Line 5 accesses intervals[0] without checking if intervals is empty before append, which is safe here but if input was empty, intervals[0] is newInterval, so no crash.

3. Step 3: Identify subtle bug

   Actually, no crash here, but if input intervals was empty, sorting and merging still works. The subtle bug is that if intervals was empty and newInterval is appended, the code works, but if the initial intervals list is empty and the code did not append newInterval first, line 5 would crash. So the bug is that the code assumes intervals is non-empty before append, which is not always true.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Accessing intervals[0] without empty check is risky [OK]

Hint: Accessing intervals[0] without empty check causes bug [OK]

Common Mistakes:

• Not handling empty input intervals list
• Assuming intervals always non-empty before append
• Incorrect merging when intervals just touch

4. What is the time complexity of the optimal greedy algorithm that finds the maximum number of non-overlapping intervals by sorting intervals and iterating through them once?

medium

A. O(n log n) due to sorting plus O(n) iteration, total O(n log n)

B. O(n^2) due to nested comparisons between intervals

C. O(n) since it only iterates once through the intervals

D. O(n log n) because of sorting intervals by start or end time

Solution

1. Step 1: Identify sorting cost

   Sorting intervals by start or end time takes O(n log n) time.

2. Step 2: Identify iteration cost

   Iterating through the sorted intervals to select non-overlapping ones takes O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates, total complexity is O(n log n) [OK]

Hint: Sorting dominates time complexity in interval scheduling [OK]

Common Mistakes:

• Assuming iteration alone is O(n) and ignoring sorting
• Mistaking nested loops causing O(n^2)
• Confusing sorting and iteration costs

5. If employees can have intervals with negative start or end times (e.g., [-5, 0]) or zero-length intervals, which modification to the sweep line algorithm is necessary to correctly find free time?

hard

A. Ignore zero-length intervals and ensure sorting places end events before start events at ties

B. Treat zero-length intervals as free time intervals

C. Sort events only by time, ignoring event type

D. Merge touching intervals as free time gaps

Solution

1. Step 1: Handle zero-length intervals

   Zero-length intervals like [2,2] do not represent busy time and should be ignored to avoid false free intervals.

2. Step 2: Maintain correct sorting order

   Sorting end events before start events at same time prevents reporting free time between touching intervals or zero-length intervals.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring zero-length intervals and correct sorting avoids invalid free times [OK]

Hint: Ignore zero-length intervals and sort end before start events [OK]

Common Mistakes:

• Counting zero-length intervals as free time
• Sorting start before end events