Merge Intervals (LeetCode 56)
You're given an array of intervals, each entry [start_i, end_i]. Fuse together every pair of intervals that overlap, then return the resulting array of non-overlapping intervals that together cover the exact same span as the original input.
Worked Examples
intervals = [[1,3],[2,6],[8,10],[15,18]][[1,6],[8,10],[15,18]]intervals = [[1,4],[4,5]][[1,5]][1,4] and [4,5] share the point 4, which counts as overlapping, so they merge into [1,5].intervals = [[4,7],[1,4]][[1,7]][1,4] and [4,7] share the point 4, so they merge into [1,7]. The input does not have to be sorted.⚖️Formal Constraints & Bounds
1 <= intervals.length <= 104intervals[i].length == 20 <= start_i <= end_i <= 104
Core Insight
Sorting by start coordinate ensures all potentially overlapping intervals are adjacent in the list.
Real-World Scenario & Production Applications
Calendar availability slot consolidation (Google Calendar free/busy scheduling) and memory buffer defragmentation.
Subproblems & Recurrence Decomposition3 Phases
Sort intervals strictly by start time (intervals.sort(key=lambda x: x[0])). Guarantees that any interval overlapping with the current cluster starts before or at the same time as subsequent intervals.
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]Step-by-Step Execution Trace Table
| Step | Accumulated Interval | Incoming Interval | Overlap Check (curr.start <= prev.end) | Action Taken | Resulting merged List |
|---|---|---|---|---|---|
| 0 | [1, 3] | — | — | Seed merged with first interval | [[1, 3]] |
| 1 | [1, 3] | [2, 6] | 2 <= 3 (True) | Overlap! Extend prev[1] = max(3, 6) = 6 | [[1, 6]] |
| 2 | [1, 6] | [8, 10] | 8 <= 6 (False) | Disjoint. Append [8, 10] | [[1, 6], [8, 10]] |
| 3 | [8, 10] | [15, 18] | 15 <= 10 (False) | Disjoint. Append [15, 18] | [[1, 6], [8, 10], [15, 18]] |
| 1 | intervals.sort(key=lambda iv: iv[0]) |
| 2 | merged = [] |
| 3 | accumulated = intervals[0] |
| 4 | for incoming in intervals[1:]: |
| 5 | if incoming[0] <= accumulated[1]: |
| 6 | accumulated[1] = max(accumulated[1], incoming[1]) |
| 7 | else: |
| 8 | merged.append(accumulated) |
| 9 | accumulated = incoming |
| 10 | merged.append(accumulated) |
| 11 | return merged |
Conceptual Narrative
Checking every pair of intervals for overlap is O(N²). Sorting by start time turns the problem into a single linear scan, because overlapping intervals become guaranteed adjacent neighbors.
🧭 Conceptual Foundation & Pattern Intuition
An interval overlaps with if and only if . In an unsorted list of intervals, two overlapping intervals can be located at opposite ends of the input array, requiring pairwise comparisons to discover.
Sorting intervals by their start time establishes a fundamental invariant:
Because start times are non-decreasing, the next interval incoming can overlap with the currently accumulating interval accumulated if and only if:
If this condition holds, the intervals overlap, and we merge them by extending the end time: accumulated[1] = max(accumulated[1], incoming[1]). If the condition fails, then because all subsequent intervals will have even larger start times, accumulated is guaranteed to be disjoint from all future intervals—allowing us to finalize it (merged.append(accumulated)) and start a new interval from incoming. After the loop, the last open accumulated is appended too.
📅 The Analogy: Merging Overlapping Calendar Blocks
Imagine a messy calendar with dozens of scheduled appointments scattered across a desk. To find your free time, you don't cross-reference appointment cards at random. You line up all the cards chronologically by their start time. You pick up the earliest card (say, 9:00 AM - 10:30 AM). You look at the next card: if it starts at 10:00 AM, it overlaps, so you stretch your meeting block to end at whichever card ends later (say, 11:00 AM). If the next card starts at 1:00 PM, you know with 100% certainty that your morning block is finished—no remaining card in the pile can ever start earlier than 1:00 PM.
🔑 Why It Works
Sorting dominates the time complexity at ; the subsequent consolidation pass runs in strictly linear time with output storage.
Sorting by start only: on
[[1,4],[1,5]]a start-only sort keeps[1,4]first, so both are counted; the key(x[0], -x[1])puts[1,5]first and[1,4]is seen as covered.Using
>=instead of>:[2,4]after[1,4]hasend == prev_endand is covered;end >= prev_endwould count it.Returning the removals: the answer is how many intervals remain,
count, not how many were covered.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Merge all overlapping intervals" into non-overlapping ones that cover the same ranges: ranges on one line that must be combined.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: incoming[0] <= accumulated[1] means the two overlap (touching counts), so stretch accumulated; otherwise accumulated is finished and goes into merged.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Setting
accumulated[1] = incoming[1]instead ofmax(accumulated[1], incoming[1]): a nested interval shrinks the end, so[[1,5],[2,3],[4,6]]returns[[1,3],[4,6]]instead of[[1,6]].Skipping
intervals.sort(key=lambda iv: iv[0]): on[[2,6],[1,3]],[1,3]is absorbed into[2,6]and the answer is[[2,6]]instead of[[1,6]].
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Merge Intervals. I sort by start, then keep one open interval, accumulated. For each incoming interval, if it starts at or before accumulated's end, they overlap and I stretch the end; otherwise accumulated is finished, so I save it to merged and start again from the incoming one. That is correct because after sorting no later interval starts earlier, so once one starts past the end, nothing after it can reach back into accumulated. The trap is the end update: I take the max of both ends, because an interval nested inside another would otherwise shrink it. After the loop I save the last accumulated. Sorting makes it
O(N log N)time, withO(N)space for the sort and the output."
Complexity & Mathematical Proof
O(N log N)
Look at the execution steps: Sorting N intervals by start time takes O(N log N). Single linear pass merges overlapping intervals in O(N). Total O(N log N) time.
O(N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Sorting takes O(N) space; result list stores at most N merged intervals.
T(N) = O(N log N) + O(N) = O(N log N)
Derivation Progression
O(N log N) sort
Orders intervals chronologically by start time.
if incoming[0] <= accumulated[1]: accumulated[1] = max(accumulated[1], incoming[1])
Merges overlapping intervals in O(1) per interval.
O(N log N)
Linear pass is strictly dominated by sorting.
Variable Definitions
Total number of intervals in the input list
Memory Architecture & Bounds
O(1) Iterative
O(N) Sort buffer
O(N) Merged intervals list
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Key phrasing: "merge all overlapping intervals", "return non-overlapping intervals". In production the same merge coalesces calendar busy blocks, reserved time slots or overlapping address ranges.
. Budget: for the sort, then one pass.
Unsorted, unbounded input (ranges arriving one at a time) cannot be sorted up front. Keep the disjoint intervals in a sorted map keyed by start and, on each insert, merge the new range with the neighbours it overlaps: to find them plus the work of absorbing them.
Core Algorithmic State Invariants
- The Output Is Sorted Too
merged receives intervals in order of their starts, and each saved interval ends before the next one starts, so the result is sorted and disjoint with no second sort. A later step can binary-search it or walk it with two pointers.
- Counting Instead of Building
When only the number of merged intervals is needed, merged can be replaced by a counter that goes up where the loop would append: the same pass, with O(1) extra space besides the sort.
Merge Intervals (LeetCode 56)
You're given an array of intervals, each entry [start_i, end_i]. Fuse together every pair of intervals that overlap, then return the resulting array of non-overlapping intervals that together cover the exact same span as the original input.
Worked Examples
intervals = [[1,3],[2,6],[8,10],[15,18]][[1,6],[8,10],[15,18]]intervals = [[1,4],[4,5]][[1,5]][1,4] and [4,5] share the point 4, which counts as overlapping, so they merge into [1,5].intervals = [[4,7],[1,4]][[1,7]][1,4] and [4,7] share the point 4, so they merge into [1,7]. The input does not have to be sorted.⚖️Formal Constraints & Bounds
1 <= intervals.length <= 104intervals[i].length == 20 <= start_i <= end_i <= 104
Core Insight
Sorting by start coordinate ensures all potentially overlapping intervals are adjacent in the list.
Real-World Scenario & Production Applications
Calendar availability slot consolidation (Google Calendar free/busy scheduling) and memory buffer defragmentation.
Subproblems & Recurrence Decomposition3 Phases
Sort intervals strictly by start time (intervals.sort(key=lambda x: x[0])). Guarantees that any interval overlapping with the current cluster starts before or at the same time as subsequent intervals.
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]Step-by-Step Execution Trace Table
| Step | Accumulated Interval | Incoming Interval | Overlap Check (curr.start <= prev.end) | Action Taken | Resulting merged List |
|---|---|---|---|---|---|
| 0 | [1, 3] | — | — | Seed merged with first interval | [[1, 3]] |
| 1 | [1, 3] | [2, 6] | 2 <= 3 (True) | Overlap! Extend prev[1] = max(3, 6) = 6 | [[1, 6]] |
| 2 | [1, 6] | [8, 10] | 8 <= 6 (False) | Disjoint. Append [8, 10] | [[1, 6], [8, 10]] |
| 3 | [8, 10] | [15, 18] | 15 <= 10 (False) | Disjoint. Append [15, 18] | [[1, 6], [8, 10], [15, 18]] |
| 1 | intervals.sort(key=lambda iv: iv[0]) |
| 2 | merged = [] |
| 3 | accumulated = intervals[0] |
| 4 | for incoming in intervals[1:]: |
| 5 | if incoming[0] <= accumulated[1]: |
| 6 | accumulated[1] = max(accumulated[1], incoming[1]) |
| 7 | else: |
| 8 | merged.append(accumulated) |
| 9 | accumulated = incoming |
| 10 | merged.append(accumulated) |
| 11 | return merged |
Conceptual Narrative
Checking every pair of intervals for overlap is O(N²). Sorting by start time turns the problem into a single linear scan, because overlapping intervals become guaranteed adjacent neighbors.
🧭 Conceptual Foundation & Pattern Intuition
An interval overlaps with if and only if . In an unsorted list of intervals, two overlapping intervals can be located at opposite ends of the input array, requiring pairwise comparisons to discover.
Sorting intervals by their start time establishes a fundamental invariant:
Because start times are non-decreasing, the next interval incoming can overlap with the currently accumulating interval accumulated if and only if:
If this condition holds, the intervals overlap, and we merge them by extending the end time: accumulated[1] = max(accumulated[1], incoming[1]). If the condition fails, then because all subsequent intervals will have even larger start times, accumulated is guaranteed to be disjoint from all future intervals—allowing us to finalize it (merged.append(accumulated)) and start a new interval from incoming. After the loop, the last open accumulated is appended too.
📅 The Analogy: Merging Overlapping Calendar Blocks
Imagine a messy calendar with dozens of scheduled appointments scattered across a desk. To find your free time, you don't cross-reference appointment cards at random. You line up all the cards chronologically by their start time. You pick up the earliest card (say, 9:00 AM - 10:30 AM). You look at the next card: if it starts at 10:00 AM, it overlaps, so you stretch your meeting block to end at whichever card ends later (say, 11:00 AM). If the next card starts at 1:00 PM, you know with 100% certainty that your morning block is finished—no remaining card in the pile can ever start earlier than 1:00 PM.
🔑 Why It Works
Sorting dominates the time complexity at ; the subsequent consolidation pass runs in strictly linear time with output storage.
Sorting by start only: on
[[1,4],[1,5]]a start-only sort keeps[1,4]first, so both are counted; the key(x[0], -x[1])puts[1,5]first and[1,4]is seen as covered.Using
>=instead of>:[2,4]after[1,4]hasend == prev_endand is covered;end >= prev_endwould count it.Returning the removals: the answer is how many intervals remain,
count, not how many were covered.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Merge all overlapping intervals" into non-overlapping ones that cover the same ranges: ranges on one line that must be combined.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: incoming[0] <= accumulated[1] means the two overlap (touching counts), so stretch accumulated; otherwise accumulated is finished and goes into merged.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Setting
accumulated[1] = incoming[1]instead ofmax(accumulated[1], incoming[1]): a nested interval shrinks the end, so[[1,5],[2,3],[4,6]]returns[[1,3],[4,6]]instead of[[1,6]].Skipping
intervals.sort(key=lambda iv: iv[0]): on[[2,6],[1,3]],[1,3]is absorbed into[2,6]and the answer is[[2,6]]instead of[[1,6]].
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Merge Intervals. I sort by start, then keep one open interval, accumulated. For each incoming interval, if it starts at or before accumulated's end, they overlap and I stretch the end; otherwise accumulated is finished, so I save it to merged and start again from the incoming one. That is correct because after sorting no later interval starts earlier, so once one starts past the end, nothing after it can reach back into accumulated. The trap is the end update: I take the max of both ends, because an interval nested inside another would otherwise shrink it. After the loop I save the last accumulated. Sorting makes it
O(N log N)time, withO(N)space for the sort and the output."
Complexity & Mathematical Proof
O(N log N)
Look at the execution steps: Sorting N intervals by start time takes O(N log N). Single linear pass merges overlapping intervals in O(N). Total O(N log N) time.
O(N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Sorting takes O(N) space; result list stores at most N merged intervals.
T(N) = O(N log N) + O(N) = O(N log N)
Derivation Progression
O(N log N) sort
Orders intervals chronologically by start time.
if incoming[0] <= accumulated[1]: accumulated[1] = max(accumulated[1], incoming[1])
Merges overlapping intervals in O(1) per interval.
O(N log N)
Linear pass is strictly dominated by sorting.
Variable Definitions
Total number of intervals in the input list
Memory Architecture & Bounds
O(1) Iterative
O(N) Sort buffer
O(N) Merged intervals list
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Key phrasing: "merge all overlapping intervals", "return non-overlapping intervals". In production the same merge coalesces calendar busy blocks, reserved time slots or overlapping address ranges.
. Budget: for the sort, then one pass.
Unsorted, unbounded input (ranges arriving one at a time) cannot be sorted up front. Keep the disjoint intervals in a sorted map keyed by start and, on each insert, merge the new range with the neighbours it overlaps: to find them plus the work of absorbing them.
Core Algorithmic State Invariants
- The Output Is Sorted Too
merged receives intervals in order of their starts, and each saved interval ends before the next one starts, so the result is sorted and disjoint with no second sort. A later step can binary-search it or walk it with two pointers.
- Counting Instead of Building
When only the number of merged intervals is needed, merged can be replaced by a counter that goes up where the loop would append: the same pass, with O(1) extra space besides the sort.