LeetCode · #56

Merge Intervals Solution

Given an array of intervals, merge all overlapping intervals and return the non-overlapping result.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #56

🏗️

Pattern

Intervals — sort + merge

Given array of intervals where intervals[i] = [startᵢ, endᵢ], merge all overlapping intervals and return an array of non-overlapping intervals that cover all input ranges.

Example

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
// [1,3] and [2,6] overlap → merged to [1,6]

Constraints

• 1 ≤ intervals.length ≤ 10⁴ • intervals[i].length == 2 • 0 ≤ startᵢ ≤ endᵢ ≤ 10⁴

Section Two · Approach 1

Brute Force — O(n²)

For each interval, compare against all others to find overlaps and merge. Repeat until no more merges possible.

Problem: O(n²) comparisons per pass, possibly multiple passes. Sorting by start first means overlapping intervals are adjacent — one linear scan suffices after sorting.

Java — Sort + naive merge

 import java.util.*;
class Solution {
public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
LinkedList<int[]> res = new LinkedList<>();
for (int[] iv : intervals) {
if (res.isEmpty() || res.getLast()[1] < iv[0])
                res.add(iv); // no overlap else
res.getLast()[1] = Math.max(res.getLast()[1], iv[1]); // merge
}
return res.toArray(new int[res.size()][]);
    }
}

Python — Sort + merge

 class Solution:
def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals.sort()
        res = [intervals[0]]
for s, e in intervals[1:]:
if s > res[-1][1]:
                res.append([s, e])
else:
                res[-1][1] = max(res[-1][1], e)
return res

Metric	Value
Time	O(n log n) — dominated by sort
Space	O(n) — output array

Section Three · Approach 2

Sort + Linear Merge — O(n log n)

Sort intervals by start time. Iterate: if the current interval overlaps the last merged one (start ≤ last.end), extend the end. Otherwise, start a new merged interval.

💡 Mental model: Imagine laying colored ribbons on a timeline. Sort them left to right by their start. Walk along: if the next ribbon's start is before the current ribbon's end, they overlap — stretch the current ribbon to cover both. If the next ribbon starts after the current one ends, place a new ribbon. The result is the fewest ribbons that cover all the same ground.

Algorithm

Sort by start ascending.
Initialize result with first interval.
For each subsequent interval: if start ≤ last.end → merge (extend end). Else → append new interval.
Return result.

🎯 When to recognize this pattern: "Merge overlapping intervals." THE foundational interval problem. Sorting by start guarantees overlapping intervals are adjacent. Variants: LC 57 (Insert Interval), LC 435 (Non-overlapping — sort by end), LC 253 (Meeting Rooms II — heap for concurrent count).

Why sort by start? After sorting, if interval B's start > interval A's end, then ALL subsequent intervals also start after A (because they're sorted). So A is finalized — no future interval can overlap it. This monotonicity enables the single-pass merge.

Section Four · Trace

Visual Walkthrough

Trace for intervals = [[1,3],[2,6],[8,10],[15,18]].

Merge Intervals — Sort + Linear Scan

Section Five · Implementation

Code — Java & Python

Java — Sort + merge

 import java.util.*;
class Solution {
public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> 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()][]);
    }
}

Python — Sort + merge

 class Solution:
def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals.sort()
        res = [intervals[0]]
for s, e in intervals[1:]:
if s <= res[-1][1]:
                res[-1][1] = max(res[-1][1], e)
else:
                res.append([s, e])
return res

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force (pairwise)	O(n²)	O(n)	Multi-pass merging
Sort + merge ← optimal	O(n log n)	O(n)	Single pass after sort; can't beat O(n log n) without sorted input

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single interval	`[[1,5]]`	Return as-is.
All overlap	`[[1,4],[2,5],[3,6]]`	One merged interval [1,6].
No overlap	`[[1,2],[3,4],[5,6]]`	All unchanged.
Contained interval	`[[1,10],[2,3]]`	[2,3] is inside [1,10]. Result: [1,10].
Touching endpoints	`[[1,4],[4,5]]`	4==4 → they overlap. Merge to [1,5].

⚠ Common Mistake: Using strict less-than (start < last.end) instead of less-than-or-equal (start ≤ last.end). Intervals [1,4] and [4,5] touch at 4 and should be merged. The overlap condition is start ≤ last.end, not start < last.end.

← Back to Interval problems

LearningTree

LC 56 · Merge Intervals — Solution & Explanation | DSA Guide