Log inSign up
mediumLeetCodeNot Started

Insert Interval

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the ith interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

Example 1 · Standard Insertion with One Overlap:

Input: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
Output: [[1, 5], [6, 9]]
Explanation: Because the new interval [2, 5] overlaps with [1, 3], they are merged into [1, 5].

Example 2 · Multi-interval Bridge Merge:

Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
Output: [[1, 2], [3, 10], [12, 16]]
Explanation: The new interval [4, 8] overlaps with [3, 5], [6, 7], and [8, 10], merging them into [3, 10].

Example 3 · Empty Intervals Input:

Input: intervals = [], newInterval = [5, 7]
Output: [[5, 7]]
Explanation: Inserting into an empty array simply returns [newInterval].

Constraints:

  • 0 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 105
  • intervals is sorted by start_i in ascending order.
  • newInterval.length == 2
  • 0 <= start <= end <= 105

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Interval representation [start, end]
  • Overlap condition — max(start1, start2) <= min(end1, end2)
  • Merge Intervals fundamentals

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3-phase interval partitioning pattern.
  • Formulate interval overlap test: interval[0] <= newInterval[1] and interval[1] >= newInterval[0].
  • Handle empty input arrays and non-overlapping boundary insertions.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Merge IntervalsNon-overlapping IntervalsMeeting Rooms

1. Append and Run Merge Intervals (Brute Force)

Intuition

Add newInterval to the list, sort by start time, and merge overlapping intervals.

Algorithm

  1. 1. Append newInterval to intervals.
  2. 2. Sort intervals based on interval[0].
  3. 3. Loop through intervals: - if result is empty or result.back()[1] < current[0]: add current - else: result.back()[1] = max(result.back()[1], current[1]).
  4. 4. Return result.

Brute Force Append, Full Sort & Merge Intervals

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [[1,2], [3,5], [6,7], [8,10], [12,16]]
Current operationSTEP 1 OF 7
Phase 1 — Step 1: Step 1: Append [4, 8] to the list and sort all 6 intervals by start time
Visual state
Values and pointers at this exact step
array
S
[1,2]
[3,5]
[6,7]
[8,10]
[12,16]
0
1
↑ Insert [4,8]
2
3
4
Variables at this step
Action
Append & Sort
Sorted Count
6
Check / comparison
Append newInterval [4,8] to array, then sort all intervals by start time.
Decision / next transition
Sorted: [[1,2], [3,5], [4,8], [6,7], [8,10], [12,16]].
Why this step matters

Phase 1 — Step 1: Step 1: Append [4, 8] to the list and sort all 6 intervals by start time. Sorting costs O(N log N).

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// Brute Force Approach: Append and Merge Intervals
7vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
8 intervals.push_back(newInterval);
9 sort(intervals.begin(), intervals.end());
10
11 vector<vector<int>> merged;
12 for (const auto& interval : intervals) {
13 if (merged.empty() || merged.back()[1] < interval[0]) {
14 merged.push_back(interval);
15 } else {
16 merged.back()[1] = max(merged.back()[1], interval[1]);
17 }
18 }
19 return merged;
20}
21
22int main() {
23 vector<vector<int>> intervals = {{1, 3}, {6, 9}};
24 vector<int> newInterval = {2, 5};
25 vector<vector<int>> result = insert(intervals, newInterval);
26
27 cout << "Output: [";
28 for (int i = 0; i < result.size(); i++) {
29 cout << "[" << result[i][0] << ", " << result[i][1] << "]" << (i + 1 < result.size() ? ", " : "");
30 }
31 cout << "]" << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting N+1 intervals takes O(N log N). The merging pass takes O(N).
  • Space complexity: O(N) — Output list holds up to N+1 intervals.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Binary Search Insertion (Better)

Intuition

Locate insertion index using binary search, insert, and merge nearby intervals.

Algorithm

  1. 1. Binary search for position where newInterval[0] fits.
  2. 2. Insert newInterval at that position.
  3. 3. Traverse intervals from the left and merge overlapping segments.
  4. 4. Return merged array.

Binary Search Insertion Index + Local Merge

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [[1,2], [3,5], [6,7], [8,10], [12,16]]
Current operationSTEP 1 OF 7
Phase 1 — Insertion index = 2 (between [3,5] and [6,7]): Step 1: Use Binary Search in O(log N) to find where newInterval belongs based on start time 4
Visual state
Values and pointers at this exact step
array
S
[1,2]
[3,5]
[6,7]
[8,10]
[12,16]
0
1
↑ Target start: 4
2
3
4
Variables at this step
Search Key
4
Insertion Idx
2
Check / comparison
Binary search for start time 4 among sorted start times: [1, 3, 6, 8, 12].
Decision / next transition
Insertion index = 2 (between [3,5] and [6,7]).
Why this step matters

Phase 1 — Insertion index = 2 (between [3,5] and [6,7]): Step 1: Use Binary Search in O(log N) to find where newInterval belongs based on start time 4.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// Better Approach: Binary Search Insertion
7vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
8 auto it = lower_bound(intervals.begin(), intervals.end(), newInterval,
9 [](const vector<int>& a, const vector<int>& b) {
10 return a[0] < b[0];
11 });
12 intervals.insert(it, newInterval);
13
14 vector<vector<int>> merged;
15 for (const auto& interval : intervals) {
16 if (merged.empty() || merged.back()[1] < interval[0]) {
17 merged.push_back(interval);
18 } else {
19 merged.back()[1] = max(merged.back()[1], interval[1]);
20 }
21 }
22 return merged;
23}
24
25int main() {
26 vector<vector<int>> intervals = {{1, 2}, {6, 7}, {8, 10}};
27 vector<int> newInterval = {3, 5};
28 vector<vector<int>> result = insert(intervals, newInterval);
29
30 cout << "Output: [";
31 for (int i = 0; i < result.size(); i++) {
32 cout << "[" << result[i][0] << ", " << result[i][1] << "]" << (i + 1 < result.size() ? ", " : "");
33 }
34 cout << "]" << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N) — Binary search takes O(log N). Array insertion and scan takes O(N) due to element shifting.
  • Space complexity: O(N) — Requires O(N) space for output list.

3. 3-Phase Linear Scan (Optimal)

Intuition

Single pass in O(N) time: add left disjoint, merge overlapping intervals into newInterval, add right disjoint.

Algorithm

  1. 1. Initialize i = 0, result = [].
  2. 2. (Phase 1): While i < N and intervals[i][1] < newInterval[0]: result.push(intervals[i++]).
  3. 3. (Phase 2): 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++ - result.push(newInterval).
  4. 4. (Phase 3): While i < N: result.push(intervals[i++]).
  5. 5. Return result.

3-Phase Single Linear Scan (Left, Merge, Right)

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [[1,2], [3,5], [6,7], [8,10], [12,16]]
Current operationSTEP 1 OF 7
Phase 1 — Push [1,2] to result Advance i to 1: Step 1 (Phase 1 — Non-overlapping Left): Interval [1, 2] ends at 2, strictly before newInterval starts at 4
Visual state
Values and pointers at this exact step
array
S
[1,2]
[3,5]
[6,7]
[8,10]
[12,16]
0
↑ Phase 1: i=0
1
2
3
4
Variables at this step
Phase
1 (Left Non-overlapping)
i
0
result
[[1,2]]
Check / comparison
Phase 1: While interval.end < newInterval.start (2 < 4): Push directly.
Decision / next transition
Push [1,2] to result. Advance i to 1.
Why this step matters

Phase 1 — Push [1,2] to result Advance i to 1: Step 1 (Phase 1 — Non-overlapping Left): Interval [1, 2] ends at 2, strictly before newInterval starts at 4. Push [1, 2] to result.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// Optimal Approach: 3-Phase Linear Scan
7vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
8 vector<vector<int>> result;
9 int i = 0, n = intervals.size();
10
11 // Phase 1: Add all intervals before newInterval
12 while (i < n && intervals[i][1] < newInterval[0]) {
13 result.push_back(intervals[i]);
14 i++;
15 }
16
17 // Phase 2: Merge overlapping intervals into newInterval
18 while (i < n && intervals[i][0] <= newInterval[1]) {
19 newInterval[0] = min(newInterval[0], intervals[i][0]);
20 newInterval[1] = max(newInterval[1], intervals[i][1]);
21 i++;
22 }
23 result.push_back(newInterval);
24
25 // Phase 3: Add all intervals after newInterval
26 while (i < n) {
27 result.push_back(intervals[i]);
28 i++;
29 }
30
31 return result;
32}
33
34int main() {
35 vector<vector<int>> intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
36 vector<int> newInterval = {4, 8};
37 vector<vector<int>> result = insert(intervals, newInterval);
38
39 cout << "Output: [";
40 for (int i = 0; i < result.size(); i++) {
41 cout << "[" << result[i][0] << ", " << result[i][1] << "]" << (i + 1 < result.size() ? ", " : "");
42 }
43 cout << "]" << endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass through the array visiting each interval exactly once.
  • Space complexity: O(N) — Result array stores at most N + 1 intervals.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Append & SortO(N log N)O(N)Append newInterval to intervals, sort by start time, and run Merge Intervals.Sorting an already sorted list.
2.Optimal — 3-Phase Linear ScanO(N)O(N)Single pass: append left disjoint intervals, merge overlaps into newInterval, append right disjoint intervals.None; industry-standard optimal solution.
3.Alternative — Binary Search InsertionOptimalO(N)O(N)Binary search insertion position, then merge overlap window.Array memory movement.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty initial array: intervals = [], newInterval = [5, 7] -> returns [[5, 7]].
  • New interval completely before all intervals: new = [0, 0], intervals = [[1, 5]] -> returns [[0, 0], [1, 5]].
  • New interval engulfs all existing intervals: new = [0, 100], intervals = [[1, 2], [3, 4]] -> returns [[0, 100]].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Insert Interval?

2.Why is the brute force approach suboptimal for large inputs in Insert Interval?

3.Which data structure or technique enables the optimal solution for Insert Interval?

Back to DSA Sheet