Bird
Raised Fist0
Interview PrepintervalsmediumFacebookAmazonGoogleMicrosoftBloomberg

Merge Intervals

Choose your preparation mode4 modes available
🎯
Merge Intervals
mediumINTERVALSFacebookAmazonGoogle

Imagine you have a calendar with multiple booked time slots, and you want to combine overlapping meetings to see your free time clearly.

💡 This problem is about combining overlapping intervals into one continuous interval. Beginners often struggle because they don't realize sorting the intervals by start time simplifies merging, and they try to compare every interval with every other, leading to inefficient solutions.
📋
Problem Statement

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

1 ≤ intervals.length ≤ 10^5intervals[i].length == 20 ≤ start_i ≤ end_i ≤ 10^9
💡
Example
Input"[[1,3],[2,6],[8,10],[15,18]]"
Output[[1,6],[8,10],[15,18]]

Intervals [1,3] and [2,6] overlap and are merged into [1,6]. The others do not overlap.

  • Single interval → output is the same single interval
  • All intervals non-overlapping → output is the same as input
  • All intervals overlapping → output is one merged interval
  • Intervals with same start and end points → merged correctly
⚠️
Common Mistakes
Not sorting intervals before merging

Incorrect merges or missed overlaps

✅ Always sort intervals by start time before merging

Modifying the list while iterating without adjusting indices

Index errors or skipping intervals

✅ Use careful index management or iterate backwards when removing elements

Not updating the end time correctly when merging

Merged intervals are incorrect or incomplete

✅ Update the end time to the max of overlapping intervals

Returning the original intervals array without slicing after in-place merge

Extra intervals remain in output, causing wrong results

✅ Return only the portion of the array up to the last merged index

🧠
Brute Force (Nested Loops Checking Overlaps)
💡 This approach exists to understand the problem deeply by checking every pair of intervals for overlap. It is inefficient but helps grasp the merging concept.

Intuition

Compare each interval with every other to check if they overlap, merge them if they do, and repeat until no more merges are possible.

Algorithm

  1. Initialize a list to hold merged intervals.
  2. For each interval, compare it with every other interval to check for overlap.
  3. If two intervals overlap, merge them into one interval.
  4. Repeat the process until no intervals can be merged further.
💡 This algorithm is hard to see as efficient because it involves repeated comparisons and merges, which can be confusing at first.
</>
Code
def merge(intervals):
    merged = []
    intervals = intervals[:]  # copy to avoid modifying input
    while intervals:
        current = intervals.pop(0)
        i = 0
        while i < len(intervals):
            if current[1] >= intervals[i][0] and intervals[i][1] >= current[0]:
                current = [min(current[0], intervals[i][0]), max(current[1], intervals[i][1])]
                intervals.pop(i)
            else:
                i += 1
        merged.append(current)
    return merged

# Driver code
if __name__ == '__main__':
    intervals = [[1,3],[2,6],[8,10],[15,18]]
    print(merge(intervals))
Line Notes
merged = []Initialize list to store merged intervals to accumulate results.
intervals = intervals[:] # copy to avoid modifying inputCopy input to avoid side effects on original data.
while intervals:Process intervals until all have been merged and removed.
current = intervals.pop(0)Pick the first interval to compare and merge with others.
while i < len(intervals):Iterate over remaining intervals to check for overlaps.
if current[1] >= intervals[i][0] and intervals[i][1] >= current[0]:Check if current interval overlaps with intervals[i].
current = [min(current[0], intervals[i][0]), max(current[1], intervals[i][1])]Merge overlapping intervals by updating start and end.
intervals.pop(i)Remove merged interval to avoid reprocessing it.
else: i += 1Move to next interval if no overlap found.
merged.append(current)Add the fully merged interval to the result list.
import java.util.*;
public class MergeIntervals {
    public static List<int[]> merge(int[][] intervals) {
        List<int[]> merged = new ArrayList<>();
        List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
        while (!list.isEmpty()) {
            int[] current = list.remove(0);
            int i = 0;
            while (i < list.size()) {
                int[] interval = list.get(i);
                if (current[1] >= interval[0] && interval[1] >= current[0]) {
                    current[0] = Math.min(current[0], interval[0]);
                    current[1] = Math.max(current[1], interval[1]);
                    list.remove(i);
                } else {
                    i++;
                }
            }
            merged.add(current);
        }
        return merged;
    }
    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        List<int[]> result = merge(intervals);
        for (int[] interval : result) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}
Line Notes
List<int[]> merged = new ArrayList<>();Initialize list to store merged intervals.
List<int[]> list = new ArrayList<>(Arrays.asList(intervals));Copy input array to a modifiable list.
while (!list.isEmpty()) {Process intervals until all are merged and removed.
int[] current = list.remove(0);Pick first interval to compare and merge.
while (i < list.size()) {Iterate over remaining intervals to check for overlaps.
if (current[1] >= interval[0] && interval[1] >= current[0]) {Check if intervals overlap.
current[0] = Math.min(current[0], interval[0]);Update start of merged interval.
current[1] = Math.max(current[1], interval[1]);Update end of merged interval.
list.remove(i);Remove merged interval to avoid reprocessing.
else { i++; }Move to next interval if no overlap.
merged.add(current);Add merged interval to result list.
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> merged;
    vector<vector<int>> list = intervals;
    while (!list.empty()) {
        vector<int> current = list[0];
        list.erase(list.begin());
        for (int i = 0; i < (int)list.size();) {
            if (current[1] >= list[i][0] && list[i][1] >= current[0]) {
                current[0] = min(current[0], list[i][0]);
                current[1] = max(current[1], list[i][1]);
                list.erase(list.begin() + i);
            } else {
                i++;
            }
        }
        merged.push_back(current);
    }
    return merged;
}

int main() {
    vector<vector<int>> intervals = {{1,3},{2,6},{8,10},{15,18}};
    vector<vector<int>> result = merge(intervals);
    for (auto &interval : result) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}
Line Notes
vector<vector<int>> merged;Initialize vector to store merged intervals.
vector<vector<int>> list = intervals;Copy input intervals for modification.
while (!list.empty()) {Process intervals until all merged.
vector<int> current = list[0];Pick first interval to compare and merge.
list.erase(list.begin());Remove picked interval from list.
for (int i = 0; i < (int)list.size();) {Iterate over remaining intervals.
if (current[1] >= list[i][0] && list[i][1] >= current[0]) {Check if intervals overlap.
current[0] = min(current[0], list[i][0]);Update start of merged interval.
current[1] = max(current[1], list[i][1]);Update end of merged interval.
list.erase(list.begin() + i);Remove merged interval to avoid reprocessing.
else { i++; }Move to next interval if no overlap.
merged.push_back(current);Add merged interval to result.
function merge(intervals) {
    let merged = [];
    intervals = intervals.slice();
    while (intervals.length > 0) {
        let current = intervals.shift();
        let i = 0;
        while (i < intervals.length) {
            if (current[1] >= intervals[i][0] && intervals[i][1] >= current[0]) {
                current = [Math.min(current[0], intervals[i][0]), Math.max(current[1], intervals[i][1])];
                intervals.splice(i, 1);
            } else {
                i++;
            }
        }
        merged.push(current);
    }
    return merged;
}

// Driver code
console.log(merge([[1,3],[2,6],[8,10],[15,18]]));
Line Notes
let merged = [];Initialize array to store merged intervals.
intervals = intervals.slice();Copy input to avoid mutating original array.
while (intervals.length > 0) {Process intervals until all merged.
let current = intervals.shift();Pick first interval to compare and merge.
while (i < intervals.length) {Iterate over remaining intervals.
if (current[1] >= intervals[i][0] && intervals[i][1] >= current[0]) {Check if intervals overlap.
current = [Math.min(current[0], intervals[i][0]), Math.max(current[1], intervals[i][1])];Merge overlapping intervals.
intervals.splice(i, 1);Remove merged interval to avoid reprocessing.
else { i++; }Move to next interval if no overlap.
merged.push(current);Add merged interval to result.
⏱
Complexity
TimeO(n^2)
SpaceO(n)

Each interval is compared with every other interval, leading to quadratic time. Space is linear for the output.

💡 For n=20 intervals, this means up to 400 comparisons, which is inefficient for large inputs.
Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps demonstrate understanding of the problem before optimizing.

🧠
Sorting + One Pass Merge
💡 Sorting intervals by start time allows merging in a single pass, which is much more efficient and easier to implement once understood.

Intuition

Sort intervals by start time, then iterate through them, merging overlapping intervals by comparing current interval start with last merged interval end.

Algorithm

  1. Sort intervals by their start time.
  2. Initialize merged list with the first interval.
  3. Iterate over remaining intervals:
  4. If current interval overlaps with last merged, merge them by updating the end.
  5. Else, add current interval to merged list.
💡 Sorting simplifies the problem by ensuring intervals are processed in order, making it easier to detect overlaps.
</>
Code
def merge(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    return merged

# Driver code
if __name__ == '__main__':
    intervals = [[1,3],[2,6],[8,10],[15,18]]
    print(merge(intervals))
Line Notes
if not intervals:Handle empty input edge case to avoid errors.
intervals.sort(key=lambda x: x[0])Sort intervals by start time to process in order.
merged = [intervals[0]]Initialize merged list with first interval as starting point.
for current in intervals[1:]:Iterate over remaining intervals to merge.
last = merged[-1]Get last merged interval to compare with current.
if current[0] <= last[1]:Check if current interval overlaps with last merged.
last[1] = max(last[1], current[1])Merge intervals by updating end time.
else: merged.append(current)No overlap, add current interval to merged list.
import java.util.*;
public class MergeIntervals {
    public static List<int[]> merge(int[][] intervals) {
        if (intervals.length == 0) return new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();
        merged.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] last = merged.get(merged.size() - 1);
            if (intervals[i][0] <= last[1]) {
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                merged.add(intervals[i]);
            }
        }
        return merged;
    }
    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        List<int[]> result = merge(intervals);
        for (int[] interval : result) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}
Line Notes
if (intervals.length == 0) return new ArrayList<>();Handle empty input to avoid errors.
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));Sort intervals by start time for ordered processing.
List<int[]> merged = new ArrayList<>();Initialize list to store merged intervals.
merged.add(intervals[0]);Add first interval as starting merged interval.
for (int i = 1; i < intervals.length; i++) {Iterate over remaining intervals.
int[] last = merged.get(merged.size() - 1);Get last merged interval for comparison.
if (intervals[i][0] <= last[1]) {Check if current interval overlaps with last merged.
last[1] = Math.max(last[1], intervals[i][1]);Merge intervals by updating end time.
else { merged.add(intervals[i]); }No overlap, add current interval to merged list.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    vector<vector<int>> merged;
    merged.push_back(intervals[0]);
    for (int i = 1; i < (int)intervals.size(); i++) {
        if (intervals[i][0] <= merged.back()[1]) {
            merged.back()[1] = max(merged.back()[1], intervals[i][1]);
        } else {
            merged.push_back(intervals[i]);
        }
    }
    return merged;
}

int main() {
    vector<vector<int>> intervals = {{1,3},{2,6},{8,10},{15,18}};
    vector<vector<int>> result = merge(intervals);
    for (auto &interval : result) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}
Line Notes
if (intervals.empty()) return {};Handle empty input to avoid errors.
sort(intervals.begin(), intervals.end(), ...Sort intervals by start time for ordered processing.
vector<vector<int>> merged;Initialize vector to store merged intervals.
merged.push_back(intervals[0]);Add first interval as starting merged interval.
for (int i = 1; i < (int)intervals.size(); i++) {Iterate over remaining intervals.
if (intervals[i][0] <= merged.back()[1]) {Check if current interval overlaps with last merged.
merged.back()[1] = max(merged.back()[1], intervals[i][1]);Merge intervals by updating end time.
else { merged.push_back(intervals[i]); }No overlap, add current interval to merged list.
function merge(intervals) {
    if (intervals.length === 0) return [];
    intervals.sort((a, b) => a[0] - b[0]);
    const merged = [intervals[0]];
    for (let i = 1; i < intervals.length; i++) {
        let last = merged[merged.length - 1];
        if (intervals[i][0] <= last[1]) {
            last[1] = Math.max(last[1], intervals[i][1]);
        } else {
            merged.push(intervals[i]);
        }
    }
    return merged;
}

// Driver code
console.log(merge([[1,3],[2,6],[8,10],[15,18]]));
Line Notes
if (intervals.length === 0) return [];Handle empty input to avoid errors.
intervals.sort((a, b) => a[0] - b[0]);Sort intervals by start time for ordered processing.
const merged = [intervals[0]];Initialize merged list with first interval.
for (let i = 1; i < intervals.length; i++) {Iterate over remaining intervals.
let last = merged[merged.length - 1];Get last merged interval for comparison.
if (intervals[i][0] <= last[1]) {Check if current interval overlaps with last merged.
last[1] = Math.max(last[1], intervals[i][1]);Merge intervals by updating end time.
else { merged.push(intervals[i]); }No overlap, add current interval to merged list.
⏱
Complexity
TimeO(n log n)
SpaceO(n)

Sorting takes O(n log n), and merging in one pass is O(n). Space is for output and sorting.

💡 For n=1000 intervals, sorting is about 10,000 operations, and merging is 1000 operations, efficient for large inputs.
Interview Verdict: Accepted / Optimal for most cases

This approach is efficient and commonly expected in interviews for merging intervals.

🧠
In-place Merge After Sorting
💡 This approach optimizes space by merging intervals in-place after sorting, reducing extra memory usage.

Intuition

Sort intervals by start time, then overwrite intervals array by merging overlapping intervals as you iterate, keeping track of the position to write merged intervals.

Algorithm

  1. Sort intervals by start time.
  2. Initialize a pointer to track position of last merged interval.
  3. Iterate over intervals starting from second interval:
  4. If current overlaps with last merged, merge by updating end.
  5. Else, move pointer forward and copy current interval.
💡 This approach is tricky because it modifies the input array directly, requiring careful pointer management.
</>
Code
def merge(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    index = 0
    for i in range(1, len(intervals)):
        if intervals[i][0] <= intervals[index][1]:
            intervals[index][1] = max(intervals[index][1], intervals[i][1])
        else:
            index += 1
            intervals[index] = intervals[i]
    return intervals[:index+1]

# Driver code
if __name__ == '__main__':
    intervals = [[1,3],[2,6],[8,10],[15,18]]
    print(merge(intervals))
Line Notes
if not intervals:Handle empty input to avoid errors.
intervals.sort(key=lambda x: x[0])Sort intervals by start time for ordered processing.
index = 0Pointer to track last merged interval position.
for i in range(1, len(intervals))Iterate over intervals starting from second.
if intervals[i][0] <= intervals[index][1]:Check if current interval overlaps with last merged.
intervals[index][1] = max(intervals[index][1], intervals[i][1])Merge intervals in-place by updating end.
else: index += 1Move pointer forward for new non-overlapping interval.
intervals[index] = intervals[i]Copy current interval to merged position.
return intervals[:index+1]Return merged intervals slice up to last merged index.
import java.util.*;
public class MergeIntervals {
    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][0];
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int index = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= intervals[index][1]) {
                intervals[index][1] = Math.max(intervals[index][1], intervals[i][1]);
            } else {
                index++;
                intervals[index] = intervals[i];
            }
        }
        return Arrays.copyOfRange(intervals, 0, index + 1);
    }
    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        int[][] result = merge(intervals);
        for (int[] interval : result) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}
Line Notes
if (intervals.length == 0) return new int[0][0];Handle empty input to avoid errors.
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));Sort intervals by start time for ordered processing.
int index = 0;Pointer to track last merged interval position.
for (int i = 1; i < intervals.length; i++) {Iterate over intervals starting from second.
if (intervals[i][0] <= intervals[index][1]) {Check if current interval overlaps with last merged.
intervals[index][1] = Math.max(intervals[index][1], intervals[i][1]);Merge intervals in-place by updating end.
else { index++; intervals[index] = intervals[i]; }Move pointer and copy new interval.
return Arrays.copyOfRange(intervals, 0, index + 1);Return merged intervals slice.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    int index = 0;
    for (int i = 1; i < (int)intervals.size(); i++) {
        if (intervals[i][0] <= intervals[index][1]) {
            intervals[index][1] = max(intervals[index][1], intervals[i][1]);
        } else {
            index++;
            intervals[index] = intervals[i];
        }
    }
    intervals.resize(index + 1);
    return intervals;
}

int main() {
    vector<vector<int>> intervals = {{1,3},{2,6},{8,10},{15,18}};
    vector<vector<int>> result = merge(intervals);
    for (auto &interval : result) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}
Line Notes
if (intervals.empty()) return {};Handle empty input to avoid errors.
sort(intervals.begin(), intervals.end(), ...Sort intervals by start time for ordered processing.
int index = 0;Pointer to track last merged interval position.
for (int i = 1; i < (int)intervals.size(); i++) {Iterate over intervals starting from second.
if (intervals[i][0] <= intervals[index][1]) {Check if current interval overlaps with last merged.
intervals[index][1] = max(intervals[index][1], intervals[i][1]);Merge intervals in-place by updating end.
else { index++; intervals[index] = intervals[i]; }Move pointer and copy new interval.
intervals.resize(index + 1);Resize vector to keep only merged intervals.
function merge(intervals) {
    if (intervals.length === 0) return [];
    intervals.sort((a, b) => a[0] - b[0]);
    let index = 0;
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= intervals[index][1]) {
            intervals[index][1] = Math.max(intervals[index][1], intervals[i][1]);
        } else {
            index++;
            intervals[index] = intervals[i];
        }
    }
    return intervals.slice(0, index + 1);
}

// Driver code
console.log(merge([[1,3],[2,6],[8,10],[15,18]]));
Line Notes
if (intervals.length === 0) return [];Handle empty input to avoid errors.
intervals.sort((a, b) => a[0] - b[0]);Sort intervals by start time for ordered processing.
let index = 0;Pointer to track last merged interval position.
for (let i = 1; i < intervals.length; i++) {Iterate over intervals starting from second.
if (intervals[i][0] <= intervals[index][1]) {Check if current interval overlaps with last merged.
intervals[index][1] = Math.max(intervals[index][1], intervals[i][1]);Merge intervals in-place by updating end.
else { index++; intervals[index] = intervals[i]; }Move pointer and copy new interval.
return intervals.slice(0, index + 1);Return merged intervals slice.
⏱
Complexity
TimeO(n log n)
SpaceO(1) additional space

Sorting is O(n log n), merging is O(n). Space is optimized by modifying input in-place.

💡 For large n, this saves memory compared to creating new lists, important in memory-constrained environments.
Interview Verdict: Accepted / Space optimized

This approach is ideal when interviewers ask for in-place or space-efficient solutions.

📊
All Approaches - One-Glance Tradeoffs
💡 Use the sorting + one pass merge approach in 95% of interviews unless space optimization is explicitly requested.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(n^2)O(n)NoN/AMention only - never code
2. Sorting + One Pass MergeO(n log n)O(n)NoN/ACode this approach
3. In-place Merge After SortingO(n log n)O(1) additionalNoN/ACode if asked for space optimization
💼
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 the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the sorting + one pass merge approach as the optimal solution.Step 4: If asked, discuss space optimization with in-place merging.Step 5: Code the chosen approach carefully, test with examples and edge cases.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your ability to recognize sorting as key, handle edge cases, write clean code, and optimize space/time.

Common Follow-ups

  • How to insert a new interval and merge? → Modify merge to handle insertion.
  • Can you do this without sorting? → Generally no, sorting is essential.
💡 These follow-ups test your ability to adapt the merge logic and understand the necessity of sorting.
🔍
Pattern Recognition

When to Use

1) Input is a list of intervals, 2) Need to combine overlapping intervals, 3) Output must be non-overlapping intervals, 4) Sorting by start time is possible.

Signature Phrases

merge overlapping intervalscombine intervalsnon-overlapping intervals

NOT This Pattern When

Problems involving intervals but requiring different techniques like interval scheduling or DP.

Similar Problems

Insert Interval - similar merging logic with insertionNon-overlapping Intervals - counting intervals after mergesMeeting Rooms - scheduling overlaps

Practice

(1/5)
1. You are given a list of non-overlapping intervals sorted by their start times, and a new interval to insert. Which approach guarantees an optimal solution that correctly merges overlapping intervals after insertion?
easy
A. Use a greedy approach that inserts the new interval at the end and merges overlapping intervals in one pass without sorting.
B. Iterate through intervals and insert the new interval in the correct position without sorting, then merge overlapping intervals.
C. Use dynamic programming to find the minimal set of merged intervals after insertion.
D. Append the new interval, sort all intervals by start time, then merge overlapping intervals in one pass.

Solution

  1. Step 1: Understand the problem constraints

    The intervals are sorted and non-overlapping initially, but inserting a new interval may cause overlaps.
  2. Step 2: Identify the approach that guarantees correct merging

    Appending and then sorting ensures the new interval is placed correctly relative to others, allowing a single pass merge to handle all overlaps reliably.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Sorting after insertion ensures correct order for merging [OK]
Hint: Sort after insertion to guarantee correct merge order [OK]
Common Mistakes:
  • Assuming intervals remain sorted after insertion without sorting
  • Trying to merge without sorting leads to missed overlaps
  • Using DP unnecessarily complicates the problem
2. Given the following code for inserting an interval, what is the final returned list after calling insert([[1,3],[6,9]], [2,5])?
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
easy
A. [[1,5],[6,9]]
B. [[1,3],[2,5],[6,9]]
C. [[1,3],[6,9],[2,5]]
D. [[1,9]]

Solution

  1. Step 1: Append and sort intervals

    After appending [2,5], intervals become [[1,3],[6,9],[2,5]]. Sorting by start time yields [[1,3],[2,5],[6,9]].
  2. Step 2: Merge overlapping intervals

    Start with merged = [[1,3]]. The next interval [2,5] overlaps since 2 <= 3, so merge to [1,5]. Next interval [6,9] does not overlap, so append it.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Result matches expected merged intervals [OK]
Hint: Sort after insertion, then merge overlapping intervals [OK]
Common Mistakes:
  • Not sorting after insertion leads to wrong order
  • Failing to merge intervals that overlap at boundaries
  • Appending newInterval multiple times
3. The following code attempts to count intervals containing each point using a line sweep. Identify the bug that causes incorrect counts for points exactly at interval ends.
medium
A. Line adding interval end event should use end + 1 instead of end.
B. Sorting key should sort points before interval starts.
C. Active count should be incremented after processing points, not before.
D. Result array initialization size is incorrect.

Solution

  1. Step 1: Identify event creation for interval ends

    Interval end events use 'end' instead of 'end + 1', so points exactly at interval end are processed after the interval ends.
  2. Step 2: Understand effect on counting

    Because end events are processed at 'end', points at 'end' see active count after decrement, missing that interval.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Changing to end + 1 fixes counting for points at interval ends [OK]
Hint: Interval end event must be at end+1 to include points at end [OK]
Common Mistakes:
  • Using end instead of end+1
  • Misordering events
  • Incorrect active count update
4. 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
5. What is the time complexity of the optimal greedy algorithm that sorts balloons by their end coordinate and then iterates once to find the minimum number of arrows?
medium
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)

Solution

  1. Step 1: Identify sorting cost

    Sorting n intervals by end coordinate takes O(n log n) time.
  2. Step 2: Identify iteration cost

    Single pass through sorted intervals is O(n).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Dominant cost is sorting, so total is O(n log n) [OK]
Hint: Sorting dominates; iteration is linear [OK]
Common Mistakes:
  • Assuming linear time because of single pass
  • Confusing with brute force O(n^2)
  • Ignoring sorting cost
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