Approach Summary
Three phases: add non-overlapping before, merge overlapping ones, add non-overlapping after.
Practice Mode
3 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Three-Phase Linear Scan (Optimal) | O(n) | O(n) | Traverse sorted list once: append non-overlapping, merge overlapping in-place, and append trailing. |
| 2 Approach 2: Append and Sort with Standard Interval Merge (Baseline) | O(n log n) | O(n) | Inserts newInterval into intervals array, sorts by start time, and merges contiguous overlapping intervals. |
| 3 Approach 2: Append and Sort with Standard Interval Merge (Baseline) | O(n log n) | O(n) | Inserts newInterval into intervals array, sorts by start time, and merges contiguous overlapping intervals. |
Step 1: Baseline
Approach 1: Three-Phase Linear Scan (Optimal)
Time: O(n)
Space: O(n)
Because the input array is already sorted, we do not need to re-sort. A single while loop scans intervals strictly prior to newInterval, a second loop absorbs all intervals that overlap by stretching newInterval bounds, and a final loop copies the remaining intervals.
Approach 1: Three-Phase Linear Scan (Optimal) Implementation
Approach 1: Three-Phase Linear Scan (Optimal)
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int i = 0, n = intervals.length;
List<int[]> result = new ArrayList<>();
while (i < n && intervals[i][1] < newInterval[0]) {
result.add(intervals[i++]);
}
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
i++;
}
result.add(newInterval);
while (i < n) {
result.add(intervals[i++]);
}
return result.toArray(new int[result.size()][2]);
}
}class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int i = 0, n = intervals.size();
vector<vector<int>> result;
while (i < n && intervals[i][1] < newInterval[0]) {
result.push_back(intervals[i++]);
}
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(intervals[i][0], newInterval[0]);
newInterval[1] = max(intervals[i][1], newInterval[1]);
i++;
}
result.push_back(newInterval);
while (i < n) {
result.push_back(intervals[i++]);
}
return result;
}
};class Solution:
def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
res = []
i, n = 0, len(intervals)
while i < n and intervals[i][1] < newInterval[0]:
res.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
res.append(newInterval)
while i < n:
res.append(intervals[i])
i += 1
return resfunction insert(intervals, newInterval) {
const result = [];
let i = 0, n = intervals.length;
while (i < n && intervals[i][1] < newInterval[0]) {
result.push(intervals[i++]);
}
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.push(newInterval);
while (i < n) {
result.push(intervals[i++]);
}
return result;
} Step 2
Approach 2: Append and Sort with Standard Interval Merge (Baseline)
Time: O(n log n)
Space: O(n)
Appends newInterval directly to intervals, sorts the collection by start time in O(n log n), and applies the classic Merge Intervals logic. Straightforward and reduces code duplication.
Approach 2: Append and Sort with Standard Interval Merge (Baseline) Implementation
Approach 2: Append and Sort with Standard Interval Merge (Baseline)
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
list.add(newInterval);
list.sort((a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] interval : list) {
if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
merged.add(interval);
} else {
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
}
}
return merged.toArray(new int[merged.size()][]);
}
}class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
intervals.push_back(newInterval);
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (auto& interval : intervals) {
if (merged.empty() || merged.back()[1] < interval[0]) {
merged.push_back(interval);
} else {
merged.back()[1] = max(merged.back()[1], interval[1]);
}
}
return merged;
}
};class Solution:
def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
intervals.append(newInterval)
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return mergedfunction insert(intervals, newInterval) {
intervals.push(newInterval);
intervals.sort((a, b) => a[0] - b[0]);
const merged = [];
for (const interval of intervals) {
if (!merged.length || merged[merged.length - 1][1] < interval[0]) {
merged.push(interval);
} else {
merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
}
}
return merged;
} Step 2: Most Optimized
Approach 2: Append and Sort with Standard Interval Merge (Baseline)
Time: O(n log n)
Space: O(n)
Appends newInterval directly to intervals, sorts the collection by start time in O(n log n), and applies the classic Merge Intervals logic. Straightforward and reduces code duplication.
Approach 2: Append and Sort with Standard Interval Merge (Baseline) Implementation
Approach 2: Append and Sort with Standard Interval Merge (Baseline)
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
list.add(newInterval);
list.sort((a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] interval : list) {
if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
merged.add(interval);
} else {
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
}
}
return merged.toArray(new int[merged.size()][]);
}
}class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
intervals.push_back(newInterval);
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (auto& interval : intervals) {
if (merged.empty() || merged.back()[1] < interval[0]) {
merged.push_back(interval);
} else {
merged.back()[1] = max(merged.back()[1], interval[1]);
}
}
return merged;
}
};class Solution:
def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
intervals.append(newInterval)
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return mergedfunction insert(intervals, newInterval) {
intervals.push(newInterval);
intervals.sort((a, b) => a[0] - b[0]);
const merged = [];
for (const interval of intervals) {
if (!merged.length || merged[merged.length - 1][1] < interval[0]) {
merged.push(interval);
} else {
merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
}
}
return merged;
}Edge Cases to Watch
- intervals is empty (returns [newInterval])
- newInterval comes entirely before all existing intervals (inserted at index 0 without merge)
- newInterval comes entirely after all existing intervals (inserted at the very end)
- newInterval engulfs all existing intervals (results in single large interval)
Algorithmic Pattern
View Pattern Guide →
Master the Intervals Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Intervals pattern.
Framework: Intervals • Interview Prep: Tested at FAANG •
Explore all Intervals problems & invariants →
How to Recognize This Pattern
- Insert and merge a new interval into sorted list
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
Array
Frequently Asked Questions
What is the optimal time and space complexity for Insert Interval?
The optimal solution for Insert Interval achieves O(n) runtime complexity and requires O(n) auxiliary space. Time complexity is O(n) because every interval in the input is inspected and appended to the output array exactly once. Space complexity is O(n) to store the result array.
How do I identify that Insert Interval requires the Intervals pattern?
In technical interviews, look for key problem signals: Insert and merge a new interval into sorted list. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Intervals strategy.
What critical edge cases must be handled in Insert Interval?
Essential edge cases to verify include: intervals is empty (returns [newInterval]); newInterval comes entirely before all existing intervals (inserted at index 0 without merge); newInterval comes entirely after all existing intervals (inserted at the very end); newInterval engulfs all existing intervals (results in single large interval). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Insert Interval?
Insert Interval is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at LinkedIn, Google, Facebook, Stripe.