Merge Intervals solution and explanation
IBM
9 more videos on this problem
Merge Intervals - Sorting - Leetcode 56NeetCode · 10:15 · 259K views
LeetCode 56. Merge Intervals (Algorithm Explained)Nick White · 12:57 · 95K views
Merge Intervals (LeetCode 56) | Full Solution with diagrams and visuals | Interview EssentialNikhil Lohia · 13:14 · 75K views
Merge Intervals - Leetcode 56 - Arrays & Strings (Python)Greg Hogg · 7:14 · 31K views
Merge Intervals | Live Coding with Explanation | Leetcode #56Algorithms Made Easy · 4:48 · 6K views
Leetcode - Merge Intervals (Python)Timothy H Chang · 6:40 · 3K views
Merge Intervals - LeetCode 56 - JavaScriptAlgoJS · 8:03 · 2K views
LeetCode 56 Merge Intervals in javascriptDev with Jovi · 5:17 · 1K views
Merge Intervals | LeetCode 56 (Medium)Destination FAANG · 18:49 · 1K views
Merge Overlapping Intervals | Brute, Optimal with Precise TC analysistake U forward · 22:35 · 470K views
The problem
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
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:
Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
Approach overview
Problem Overview: You receive a list of intervals where each interval represents a start and end time. Some intervals overlap. Your task is to merge all overlapping intervals and return a list of non‑overlapping intervals that cover the same ranges.
Approach 1: Sort and Merge Intervals (Time: O(n log n), Space: O(n))
The standard solution sorts intervals by their starting value, then performs a single linear scan to merge overlaps. Sorting ensures that if two intervals overlap, they appear next to each other. Start with the first interval and treat it as the current merged range. As you iterate through the sorted list, compare the current interval's start with the previous merged interval's end.
If the intervals overlap (current.start <= last.end), update the merged interval's end using max(last.end, current.end). If they do not overlap, push the previous interval into the result and start a new merged interval. This produces the minimal set of merged ranges in one pass after sorting. The algorithm relies on sorting followed by sequential processing of an array. Time complexity is O(n log n) due to sorting, while the merge scan itself is O(n). Space complexity is O(n) for the output list.
Approach 2: Interval Insertion Method (Time: O(n log n), Space: O(n))
This method treats the problem similarly to repeatedly inserting intervals into a merged result set. First sort the intervals by start time. Then iterate through them while maintaining a result list of non‑overlapping intervals. For each new interval, check whether it overlaps with the last interval already stored.
If there is no overlap (interval.start > result[-1].end), append it directly to the result. If an overlap exists, merge by expanding the end of the previous interval: result[-1].end = max(result[-1].end, interval.end). Conceptually, this approach views merging as incremental interval insertion into a maintained structure.
The advantage is conceptual clarity: the result array always stays valid and merged. The algorithm still requires sorting first, so the overall complexity remains O(n log n) time with O(n) space. The iteration step itself is linear.
Recommended for interviews: Interviewers typically expect the Sort and Merge approach. It demonstrates knowledge of sorting combined with linear scanning and interval reasoning. Explaining the overlap condition and why sorting guarantees adjacent overlaps shows strong problem‑solving skills. A brute force pairwise comparison would work but leads to O(n^2) complexity and signals weaker optimization awareness.
Approach 1: Sort and Merge Intervals
The key to solving this problem is to first sort the intervals based on the starting time. Once sorted, we can iterate over the intervals and merge them if they overlap. Two intervals overlap if the start of the current interval is less than or equal to the end of the previous interval.
def merge(intervals):
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 mergedimport java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return new int[0][0];
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] interval : intervals) {
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()][]);
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
merged.push_back(intervals[0]);
for (const auto& interval : intervals) {
if (merged.back()[1] >= interval[0]) {
merged.back()[1] = max(merged.back()[1], interval[1]);
} else {
merged.push_back(interval);
}
}
return merged;
}var merge = function(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
let merged = [];
for (let 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;
};#include <stdlib.h>
#include <string.h>
int compare(const void *a, const void *b) {
return (*(int **)a)[0] - (*(int **)b)[0];
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
if (intervalsSize == 0) {
*returnSize = 0;
return NULL;
}
qsort(intervals, intervalsSize, sizeof(int*), compare);
int** result = (int**)malloc(intervalsSize * sizeof(int*));
*returnColumnSizes = (int*)malloc(intervalsSize * sizeof(int));
int index = 0;
for (int i = 0; i < intervalsSize; ++i) {
if (index == 0 || result[index - 1][1] < intervals[i][0]) {
result[index] = (int*)malloc(2 * sizeof(int));
result[index][0] = intervals[i][0];
result[index][1] = intervals[i][1];
(*returnColumnSizes)[index] = 2;
index++;
} else {
result[index - 1][1] = result[index - 1][1] > intervals[i][1] ? result[index - 1][1] : intervals[i][1];
}
}
*returnSize = index;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[][] Merge(int[][] intervals) {
Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
List<int[]> merged = new List<int[]>();
foreach (var interval in intervals) {
if (merged.Count == 0 || merged[^1][1] < interval[0]) {
merged.Add(interval);
}
else {
merged[^1][1] = Math.Max(merged[^1][1], interval[1]);
}
}
return merged.ToArray();
}
}In Python, the built-in sort function is used to arrange the intervals. We iterate through and merge the overlapping intervals.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(n) due to storage requirements of the merged list.
Approach 2: Interval Insertion Method
Another approach involves consecutive comparisons and inserting intervals into a new list if they do not overlap with the current interval being processed.
def merge(intervals):
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 mergedimport java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> result = new ArrayList<>();
int[] currentInterval = intervals[0];
result.add(currentInterval);
for (int[] interval : intervals) {
if (currentInterval[1] < interval[0]) {
currentInterval = interval;
result.add(currentInterval);
} else {
currentInterval[1] = Math.max(currentInterval[1], interval[1]);
}
}
return result.toArray(new int[result.size()][]);
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end());
vector<vector<int>> result = {intervals[0]};
for (auto& interval : intervals) {
if (result.back()[1] < interval[0]) {
result.push_back(interval);
} else {
result.back()[1] = max(result.back()[1], interval[1]);
}
}
return result;
}var merge = function(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
let merged = [];
intervals.forEach(interval => {
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;
};#include <stdlib.h>
#include <string.h>
int compare(const void *a, const void *b) {
return (*(int **)a)[0] - (*(int **)b)[0];
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
if (intervalsSize == 0) {
*returnSize = 0;
return NULL;
}
qsort(intervals, intervalsSize, sizeof(int*), compare);
int** result = (int**)malloc(intervalsSize * sizeof(int*));
*returnColumnSizes = (int*)malloc(intervalsSize * sizeof(int));
int index = 0;
for (int i = 0; i < intervalsSize; ++i) {
if (index == 0 || result[index - 1][1] < intervals[i][0]) {
result[index] = (int*)malloc(2 * sizeof(int));
result[index][0] = intervals[i][0];
result[index][1] = intervals[i][1];
(*returnColumnSizes)[index] = 2;
index++;
} else {
if (result[index - 1][1] < intervals[i][1]) {
result[index - 1][1] = intervals[i][1];
}
}
}
*returnSize = index;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[][] Merge(int[][] intervals) {
Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
List<int[]> mergedIntervals = new List<int[]>();
int[] currentInterval = intervals[0];
mergedIntervals.Add(currentInterval);
foreach (var interval in intervals) {
if (currentInterval[1] < interval[0]) {
currentInterval = interval;
mergedIntervals.Add(currentInterval);
} else {
currentInterval[1] = Math.Max(currentInterval[1], interval[1]);
}
}
return mergedIntervals.ToArray();
}
}In Python, the proposal is about sorting the intervals, looping through them, and confirming whether current intervals are merged thoroughly based on the ending values.
Time Complexity: O(n log n).
Space Complexity: O(n).
Approach 3: Sorting + One-pass Traversal
We can sort the intervals in ascending order by the left endpoint, and then traverse the intervals for merging operations.
The specific merging operation is as follows.
First, we add the first interval to the answer. Then, we consider each subsequent interval in turn:
- If the right endpoint of the last interval in the answer array is less than the left endpoint of the current interval, it means that the two intervals will not overlap, so we can directly add the current interval to the end of the answer array;
- Otherwise, it means that the two intervals overlap. We need to use the right endpoint of the current interval to update the right endpoint of the last interval in the answer array, setting it to the larger of the two.
Finally, we return the answer array.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of intervals.
function merge(intervals: number[][]): number[][] {
intervals.sort((a, b) => a[0] - b[0]);
const ans: number[][] = [];
let [st, ed] = intervals[0];
for (const [s, e] of intervals.slice(1)) {
if (ed < s) {
ans.push([st, ed]);
[st, ed] = [s, e];
} else {
ed = Math.max(ed, e);
}
}
ans.push([st, ed]);
return ans;
}func merge(intervals [][]int) (ans [][]int) {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
st, ed := intervals[0][0], intervals[0][1]
for _, e := range intervals[1:] {
if ed < e[0] {
ans = append(ans, []int{st, ed})
st, ed = e[0], e[1]
} else if ed < e[1] {
ed = e[1]
}
}
ans = append(ans, []int{st, ed})
return ans
}class Solution {
fun merge(intervals: Array<IntArray>): Array<IntArray> {
intervals.sortBy { it[0] }
val result = mutableListOf<IntArray>()
val n = intervals.size
var i = 0
while (i < n) {
val left = intervals[i][0]
var right = intervals[i][1]
while (true) {
i++
if (i < n && right >= intervals[i][0]) {
right = maxOf(right, intervals[i][1])
} else {
result.add(intArrayOf(left, right))
break
}
}
}
return result.toTypedArray()
}
}impl Solution {
pub fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
intervals.sort_unstable_by(|a, b| a[0].cmp(&b[0]));
let n = intervals.len();
let mut res = vec![];
let mut i = 0;
while i < n {
let l = intervals[i][0];
let mut r = intervals[i][1];
i += 1;
while i < n && r >= intervals[i][0] {
r = r.max(intervals[i][1]);
i += 1;
}
res.push(vec![l, r]);
}
res
}
}Approach 4: Default Approach
function merge(intervals: number[][]): number[][] {
intervals.sort((a, b) => a[0] - b[0]);
const ans: number[][] = [intervals[0]];
for (let i = 1; i < intervals.length; ++i) {
if (ans.at(-1)[1] < intervals[i][0]) {
ans.push(intervals[i]);
} else {
ans.at(-1)[1] = Math.max(ans.at(-1)[1], intervals[i][1]);
}
}
return ans;
}func merge(intervals [][]int) (ans [][]int) {
sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
ans = append(ans, intervals[0])
for _, e := range intervals[1:] {
if ans[len(ans)-1][1] < e[0] {
ans = append(ans, e)
} else {
ans[len(ans)-1][1] = max(ans[len(ans)-1][1], e[1])
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sort and Merge Intervals | Time Complexity: O(n log n) for sorting. |
| Interval Insertion Method | Time Complexity: O(n log n). |
| Sorting + One-pass Traversal | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Merge Intervals | O(n log n) | O(n) | General case where intervals are unsorted. Most common and interview‑expected solution. |
| Interval Insertion Method | O(n log n) | O(n) | When building a merged result incrementally while iterating through sorted intervals. |
Frequently asked questions
Is Merge Intervals easy or hard?
Merge Intervals is considered a medium‑difficulty problem. The challenge comes from recognizing that sorting simplifies overlap detection and reduces the problem to a linear merge scan.
Merge Intervals Python/Java solution
Most implementations follow the same structure: sort intervals by start value, iterate through them, and merge overlaps by updating the previous interval's end. This logic translates directly across Python, Java, C++, C#, and JavaScript with only syntax differences.
How to solve Merge Intervals in O(n)?
O(n) time is possible only if the intervals are already sorted by start time. In that case, you simply iterate through the list once and merge overlapping intervals by comparing the current start with the previous end. Without sorted input, sorting is required, which increases complexity to O(n log n).
What is the best approach for Merge Intervals?
The best approach sorts the intervals by start time and then performs a single linear pass to merge overlaps. During the scan, compare each interval with the last merged interval and extend the end if they overlap. This solution runs in O(n log n) time due to sorting and O(n) space for the output list.
Is Merge Intervals asked at Google/Amazon/Meta?
Merge Intervals is a common interview problem at major tech companies including Google, Amazon, Meta, and Microsoft. It tests sorting, interval reasoning, and edge‑case handling. Variations of the problem often appear in system design or scheduling related questions.
What data structure is used in Merge Intervals?
The problem primarily uses arrays or lists to store intervals and results. Sorting algorithms organize the intervals by start time, and a dynamic result list keeps track of merged intervals during iteration.
What is the time complexity of Merge Intervals?
The optimal solution runs in O(n log n) time because the intervals must be sorted by their starting value. After sorting, the merge step requires only one linear scan, which is O(n). Space complexity is typically O(n) to store the merged intervals.