#131 Medium Time O(n log n) Space O(n) Animated

Merge Intervals

Merge all overlapping intervals.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Sort intervals, then maintain one boundary

After sorting, overlap decisions depend only on the active interval and the next start.

Approach: Sort & Merge

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

After sorting, overlap decisions depend only on the active interval and the next start.

Common Pitfall

Compare the next start against the current end, not against the original unsorted input.

Description

Merge all overlapping intervals.

Constraints

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution — Sort & Merge

TimeO(n log n) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Sort by the relevant endpoint.
Initialize the active interval.
Merge or select based on overlap.
Update the active boundary.

def merge(intervals):
    intervals.sort(key=lambda i: i[0])
    output = [intervals[0]]
    
    for start, end in intervals[1:]:
        lastEnd = output[-1][1]
        
        if start <= lastEnd:
            output[-1][1] = max(lastEnd, end)
        else:
            output.append([start, end])
            
    return output

Insert Interval

Non-overlapping Intervals

Merge Intervals

Steps

Description

Constraints

Tags

Solution — Sort & Merge