Approach Summary
Sort by start. Merge current with last result if overlapping. Two intervals overlap when start2 <= end1.
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: Sort by Start Time and Merge (Optimal) | O(n log n) | O(n) | Sort intervals by start coordinate, merging with the previous interval whenever start <= previous end. |
| 2 Approach 2: Connected Components Graph-Based Merging (Baseline) | O(n²) | O(n) | Builds an overlap graph where intersecting intervals share edges, merging nodes per connected component. |
| 3 Approach 2: Connected Components Graph-Based Merging (Baseline) | O(n²) | O(n) | Builds an overlap graph where intersecting intervals share edges, merging nodes per connected component. |
Step 1: Baseline
Approach 1: Sort by Start Time and Merge (Optimal)
Time: O(n log n)
Space: O(n)
Sorting by start time ensures that any intervals that could potentially overlap appear consecutively. A single pass compares the current interval start with the previous merged interval end.
Approach 1: Sort by Start Time and Merge (Optimal) Implementation
Approach 1: Sort by Start Time and Merge (Optimal)
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> res = new ArrayList<>();
for (int[] iv : intervals) {
if (res.isEmpty() || res.get(res.size() - 1)[1] < iv[0]) {
res.add(iv);
} else {
res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], iv[1]);
}
}
return res.toArray(new int[res.size()][]);
}
}class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto& iv : intervals) {
if (res.empty() || res.back()[1] < iv[0]) {
res.push_back(iv);
} else {
res.back()[1] = max(res.back()[1], iv[1]);
}
}
return res;
}
};class Solution:
def merge(self, intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0])
res = []
for iv in intervals:
if not res or res[-1][1] < iv[0]:
res.append(iv)
else:
res[-1][1] = max(res[-1][1], iv[1])
return resfunction merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const res = [];
for (const iv of intervals) {
if (!res.length || res[res.length - 1][1] < iv[0]) {
res.push(iv);
} else {
res[res.length - 1][1] = Math.max(res[res.length - 1][1], iv[1]);
}
}
return res;
} Step 2
Approach 2: Connected Components Graph-Based Merging (Baseline)
Time: O(n²)
Space: O(n)
Constructs an undirected graph where each interval is a node and an edge connects interval i and j if max(i.start, j.start) <= min(i.end, j.end). Performs BFS/DFS to identify connected components, outputting [min(starts), max(ends)] for each component.
Approach 2: Connected Components Graph-Based Merging (Baseline) Implementation
Approach 2: Connected Components Graph-Based Merging (Baseline)
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> res = new ArrayList<>();
for (int[] interval : intervals) {
if (res.isEmpty() || res.get(res.size() - 1)[1] < interval[0]) {
res.add(interval);
} else {
res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], interval[1]);
}
}
return res.toArray(new int[res.size()][]);
}
}class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto& interval : intervals) {
if (res.empty() || res.back()[1] < interval[0]) {
res.push_back(interval);
} else {
res.back()[1] = max(res.back()[1], interval[1]);
}
}
return res;
}
};class Solution:
def merge(self, intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0])
res = []
for interval in intervals:
if not res or res[-1][1] < interval[0]:
res.append(interval)
else:
res[-1][1] = max(res[-1][1], interval[1])
return resfunction merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const res = [];
for (const interval of intervals) {
if (!res.length || res[res.length - 1][1] < interval[0]) {
res.push(interval);
} else {
res[res.length - 1][1] = Math.max(res[res.length - 1][1], interval[1]);
}
}
return res;
} Step 2: Most Optimized
Approach 2: Connected Components Graph-Based Merging (Baseline)
Time: O(n²)
Space: O(n)
Constructs an undirected graph where each interval is a node and an edge connects interval i and j if max(i.start, j.start) <= min(i.end, j.end). Performs BFS/DFS to identify connected components, outputting [min(starts), max(ends)] for each component.
Approach 2: Connected Components Graph-Based Merging (Baseline) Implementation
Approach 2: Connected Components Graph-Based Merging (Baseline)
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> res = new ArrayList<>();
for (int[] interval : intervals) {
if (res.isEmpty() || res.get(res.size() - 1)[1] < interval[0]) {
res.add(interval);
} else {
res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], interval[1]);
}
}
return res.toArray(new int[res.size()][]);
}
}class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto& interval : intervals) {
if (res.empty() || res.back()[1] < interval[0]) {
res.push_back(interval);
} else {
res.back()[1] = max(res.back()[1], interval[1]);
}
}
return res;
}
};class Solution:
def merge(self, intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0])
res = []
for interval in intervals:
if not res or res[-1][1] < interval[0]:
res.append(interval)
else:
res[-1][1] = max(res[-1][1], interval[1])
return resfunction merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const res = [];
for (const interval of intervals) {
if (!res.length || res[res.length - 1][1] < interval[0]) {
res.push(interval);
} else {
res[res.length - 1][1] = Math.max(res[res.length - 1][1], interval[1]);
}
}
return res;
}Edge Cases to Watch
- Single interval (e.g. [[1, 4]]; returns [[1, 4]])
- All intervals overlap into one (e.g. [[1, 4], [2, 5], [3, 6]]; returns [[1, 6]])
- No overlapping intervals (e.g. [[1, 2], [3, 4], [5, 6]]; returns identical list)
- Touching intervals (e.g. [1, 4] and [4, 5] touch at 4; merged into [1, 5])
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
- Merge overlapping intervals
- Sort by start
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(n)
Tags
Array Sorting
Frequently Asked Questions
What is the optimal time and space complexity for Merge Intervals?
The optimal solution for Merge Intervals achieves O(n log n) runtime complexity and requires O(n) auxiliary space. Time complexity is O(n log n) dominated by the initial sorting step. The linear scan takes O(n). Space complexity is O(n) or O(log n) depending on the sorting implementation.
How do I identify that Merge Intervals requires the Intervals pattern?
In technical interviews, look for key problem signals: Merge overlapping intervals; Sort by start. 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 Merge Intervals?
Essential edge cases to verify include: Single interval (e.g. [[1, 4]]; returns [[1, 4]]); All intervals overlap into one (e.g. [[1, 4], [2, 5], [3, 6]]; returns [[1, 6]]); No overlapping intervals (e.g. [[1, 2], [3, 4], [5, 6]]; returns identical list); Touching intervals (e.g. [1, 4] and [4, 5] touch at 4; merged into [1, 5]). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Merge Intervals?
Merge Intervals is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Facebook, Amazon, Google, Twitter, Stripe.