Log inSign up
mediumLeetCodeNot Started

Merge Intervals

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

Arrays
Solve on LeetCode
Lesson

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.

Example 1 · Overlapping Chain:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].

Example 2 · Touching Boundaries:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
Explanation: Intervals [1, 4] and [4, 5] touch at boundary 4 and are considered overlapping.

Example 3 · Already Disjoint Intervals:

Input: intervals = [[1, 2], [3, 4], [5, 6]]
Output: [[1, 2], [3, 4], [5, 6]]
Explanation: No intervals overlap, so the original list is returned.

Constraints:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Interval representation [start, end]
  • Custom array sorting using comparator functions or lambdas
  • Greedy interval boundary tracking

What You'll Learn

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

  • Master interval sorting using standard language comparators.
  • Correctly detect interval overlap (current.start <= previous.end).
  • Handle fully subsumed intervals using max(previous.end, current.end).

Pattern Recognition Trigger

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

Signals to Look For:

  • Given a collection of intervals or time ranges that may overlap or touch.
  • Need to compress, merge, or remove overlapping segments.
  • Start times are initially unsorted.

Algorithmic Decision Tree:

  • When managing overlapping intervals: Sort by start time, then linearly merge contiguous overlapping endpoints where current.start <= previous.end.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Graph of Overlapping Intervals / Nested Merges

Intuition

Iteratively compare pairs of intervals and merge any overlapping pair until no more merges can occur.

Algorithm

  1. 1. Maintain a list of intervals.
  2. 2. Repeatedly scan all pairs (i, j). If intervals[i] and intervals[j] overlap, merge them into intervals[i] and remove intervals[j].
  3. 3. Repeat until a full pass makes 0 merges.
  4. 4. Return merged intervals list.

Brute Force Pairwise Overlap Graph Merging

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [[1,3], [2,6], [8,10], [15,18]]
Current operationSTEP 1 OF 6
Compare Intervals 0 and 1: [1, 3] and [2, 6] overlap because 2 <= 3
Visual state
Values and pointers at this exact step
table
S
[1,3]
[2,6]
[8,10]
[15,18]
0
↑ i=0 [1,3]
1
↑ j=1 [2,6]
2
3
Interval 0[1,3]
Interval 1[2,6]
Merged[1,6]
OverlapYES
Variables at this step
Interval 0
[1,3]
Interval 1
[2,6]
Merged
[1,6]
Overlap
YES
Check / comparison
curr.start (2) <= prev.end (3). Intervals overlap!
Decision / next transition
Merge into [1, max(3, 6) = 6]. Replace [1,3] with [1,6].
Why this step matters

Compare Intervals 0 and 1: [1, 3] and [2, 6] overlap because 2 <= 3. Merge them into [1, 6].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<vector<int>> merge(vector<vector<int>>& intervals) {
17 bool merged = true;
18 while (merged) {
19 merged = false;
20 for (size_t i = 0; i < intervals.size(); ++i) {
21 for (size_t j = i + 1; j < intervals.size(); ++j) {
22 if (max(intervals[i][0], intervals[j][0]) <= min(intervals[i][1], intervals[j][1])) {
23 intervals[i][0] = min(intervals[i][0], intervals[j][0]);
24 intervals[i][1] = max(intervals[i][1], intervals[j][1]);
25 intervals.erase(intervals.begin() + j);
26 merged = true;
27 break;
28 }
29 }
30 if (merged) break;
31 }
32 }
33 return intervals;
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
40 vector<vector<int>> res = sol.merge(intervals);
41 cout << "Merged Intervals:" << endl;
42 for (const auto& interval : res) {
43 cout << "[" << interval[0] << ", " << interval[1] << "] ";
44 }
45 cout << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N^2) — Repeated pair scanning and list modifications can take up to O(N2) time.
  • Space complexity: O(N) — Requires extra memory to manage dynamically mutating lists of 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. Sort and Auxiliary Stack

Intuition

Sort intervals by start time ascending, then push onto a stack while merging top interval if overlapping.

Algorithm

  1. 1. Sort intervals by start time ascending.
  2. 2. Initialize stack of intervals with intervals[0].
  3. 3. For i from 1 to n-1: - If intervals[i][0] <= stack.top()[1], update stack.top()[1] = max(stack.top()[1], intervals[i][1]). - Else push intervals[i] onto stack.
  4. 4. Convert stack to output list.

Sort and Stack Buffer Interval Merging Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [[1,3], [2,6], [8,10], [15,18]]
Current operationSTEP 1 OF 6
Step 1 — Push Initial Interval: Push [1, 3] onto stack buffer
Visual state
Values and pointers at this exact step
table
S
[1,3]
[2,6]
[8,10]
[15,18]
0
↑ Push [1,3]
1
2
3
Stack[[1, 3]]
Variables at this step
Stack
[[1, 3]]
Check / comparison
Stack is empty. Push first interval [1, 3].
Decision / next transition
Stack: [[1, 3]]. Advance to interval 1.
Why this step matters

Step 1 — Push Initial Interval: Push [1, 3] onto stack buffer.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<vector<int>> merge(vector<vector<int>>& intervals) {
17 sort(intervals.begin(), intervals.end());
18 stack<vector<int>> st;
19 st.push(intervals[0]);
20
21 for (size_t i = 1; i < intervals.size(); ++i) {
22 auto& top = st.top();
23 if (intervals[i][0] <= top[1]) {
24 top[1] = max(top[1], intervals[i][1]);
25 } else {
26 st.push(intervals[i]);
27 }
28 }
29
30 vector<vector<int>> result(st.size());
31 for (int i = st.size() - 1; i >= 0; --i) {
32 result[i] = st.top();
33 st.pop();
34 }
35 return result;
36 }
37};
38
39int main() {
40 Solution sol;
41 vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
42 vector<vector<int>> res = sol.merge(intervals);
43 cout << "Merged Intervals:" << endl;
44 for (const auto& interval : res) {
45 cout << "[" << interval[0] << ", " << interval[1] << "] ";
46 }
47 cout << endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting takes O(N log N). Stack operations process each interval once in O(N).
  • Space complexity: O(N) — Requires auxiliary stack to hold merged intervals, consuming O(N) memory.

3. Sort & Direct In-Place Merging (Optimal & Standard)

Intuition

Sort by start time, append the first interval to result, and dynamically extend the last interval's end.

Algorithm

  1. 1. If intervals is empty, return [].
  2. 2. Sort intervals by start time: intervals.sort((a, b) => a[0] - b[0]).
  3. 3. Initialize merged = [intervals[0]].
  4. 4. For each interval curr from index 1 to n-1: - Let last = merged[merged.length - 1]. - If curr[0] <= last[1]: last[1] = max(last[1], curr[1]). - Else: merged.push(curr).
  5. 5. Return merged list.

In-Place Sort + Single Greedy Linear Scan Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [[1,3], [2,6], [8,10], [15,18]]
Current operationSTEP 1 OF 6
Step 1 — Sorting: Intervals sorted by start
Visual state
Values and pointers at this exact step
table
S
[1,3]
[2,6]
[8,10]
[15,18]
0
↑ Sort & Initialize
1
2
3
merged[[1, 3]]
ActionInitialize
Variables at this step
merged
[[1, 3]]
Action
Initialize
Check / comparison
Sorted by start time: [[1, 3], [2, 6], [8, 10], [15, 18]]. Initialize res = [[1, 3]].
Decision / next transition
merged = [[1, 3]].
Why this step matters

Step 1 — Sorting: Intervals sorted by start. Place [1, 3] as initial interval.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 vector<vector<int>> merge(vector<vector<int>>& intervals) {
17 if (intervals.empty()) return {};
18 sort(intervals.begin(), intervals.end());
19 vector<vector<int>> merged;
20 merged.push_back(intervals[0]);
21
22 for (size_t i = 1; i < intervals.size(); ++i) {
23 if (intervals[i][0] <= merged.back()[1]) {
24 merged.back()[1] = max(merged.back()[1], intervals[i][1]);
25 } else {
26 merged.push_back(intervals[i]);
27 }
28 }
29 return merged;
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
36 vector<vector<int>> res = sol.merge(intervals);
37 cout << "Merged Intervals:" << endl;
38 for (const auto& interval : res) {
39 cout << "[" << interval[0] << ", " << interval[1] << "] ";
40 }
41 cout << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting takes O(N log N). The single pass to merge intervals takes O(N).
  • Space complexity: O(1) — Output list does not count toward auxiliary space. Extra space is O(1).

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Graph of Overlapping Intervals / Nested MergesO(N^2)O(N)Iteratively compare pairs of intervals and merge any overlapping pair until no more merges can occur.Repeated redundant scans over the input.
2.Approach 2: Sort and Auxiliary StackO(N log N)O(N)Sort intervals by start time ascending, then push onto a stack while merging top interval if overlapping.Auxiliary memory allocation or sorting step.
3.Approach 3: Sort & Direct In-Place Merging (Optimal & Standard)OptimalO(N log N)O(1)Sort by start time, append the first interval to result, and dynamically extend the last interval's end.None. Asymptotically optimal.

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:

  • Fully Nested Intervals [[1, 10], [2, 3], [4, 8]] — Input: `, Expected: ` —
  • Already Sorted Disjoint Intervals [[1, 2], [3, 4]] — Input: `, Expected: ` —
  • Single Interval [[1, 5]] — Input: `, Expected: ` —

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 Merge Intervals?

2.Why is the brute force approach suboptimal for large inputs in Merge Intervals?

3.Which data structure or technique enables the optimal solution for Merge Intervals?

Back to DSA Sheet