56. Merge Intervals (Medium)

Problem

Given an array of intervals where each interval is [start, end], merge all overlapping intervals and return the resulting non-overlapping list.

Example

intervals = [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
intervals = [[1,4],[4,5]] → [[1,5]]

LeetCode 56 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, quadratic merge

Repeatedly find any pair of overlapping intervals and merge them until none remain.

def merge(intervals):
    intervals = [list(iv) for iv in intervals]
    changed = True
    while changed:                         # L1: outer fixed-point loop
        changed = False
        result = []
        for iv in intervals:               # L2: scan every interval
            for existing in result:        # L3: against every kept one
                if iv[0] <= existing[1] and existing[0] <= iv[1]:
                    existing[0] = min(existing[0], iv[0])
                    existing[1] = max(existing[1], iv[1])
                    changed = True
                    break
            else:
                result.append(iv)
        intervals = result
    return intervals

function merge(intervals: number[][]): number[][] {
    let ivs = intervals.map(iv => [...iv]);
    let changed = true;
    while (changed) {                              // L1: outer fixed-point loop
        changed = false;
        const result: number[][] = [];
        for (const iv of ivs) {                   // L2: scan every interval
            let merged = false;
            for (const existing of result) {       // L3: against every kept one
                if (iv[0] <= existing[1] && existing[0] <= iv[1]) {
                    existing[0] = Math.min(existing[0], iv[0]);
                    existing[1] = Math.max(existing[1], iv[1]);
                    changed = true;
                    merged = true;
                    break;
                }
            }
            if (!merged) result.push([...iv]);
        }
        ivs = result;
    }
    return ivs;
}

func merge(intervals [][]int) [][]int {
    changed := true
    for changed {                                   // L1: outer fixed-point loop
        changed = false
        result := [][]int{}
        for _, iv := range intervals {              // L2: scan every interval
            merged := false
            for _, existing := range result {       // L3: against every kept one
                if iv[0] <= existing[1] && existing[0] <= iv[1] {
                    if iv[0] < existing[0] { existing[0] = iv[0] }
                    if iv[1] > existing[1] { existing[1] = iv[1] }
                    changed = true
                    merged = true
                    break
                }
            }
            if !merged {
                result = append(result, []int{iv[0], iv[1]})
            }
        }
        intervals = result
    }
    return intervals
}

final class Solution {
    func merge(_ intervals: [[Int]]) -> [[Int]] {
        var values = intervals
        var changed = true
        while changed {
            changed = false
            outer: for left in 0..<values.count {
                for right in (left + 1)..<values.count {
                    if max(values[left][0], values[right][0]) <= min(values[left][1], values[right][1]) {
                        values[left] = [min(values[left][0], values[right][0]), max(values[left][1], values[right][1])]
                        values.remove(at: right)
                        changed = true
                        break outer
                    }
                }
            }
        }
        return values.sorted { $0[0] < $1[0] }
    }
}

Each outer pass touches every pair (L2 × L3 = $O(n²)$ ). The outer loop runs until a pass produces no merges; in the worst case (a chain like [[1,2],[2,3],[3,4],...]) that’s another $O(n)$ factor → $O(n³)$ overall.

Complexity

Time: $O(n²)$ or worse.
Space: $O(n)$ .

Approach 2: Sort by start + linear merge (canonical)

Sort; then walk, merging each new interval into the last of the result if they overlap, else appending.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])   # L1: O(n log n)
    result = []                            # L2: O(1) setup
    for interval in intervals:             # L3: O(n) iterations
        if result and interval[0] <= result[-1][1]:    # L4: O(1) check
            result[-1][1] = max(result[-1][1], interval[1])  # L5: O(1) extend
        else:
            result.append(list(interval))  # L6: O(1) amortized
    return result

function merge(intervals: number[][]): number[][] {
    intervals.sort((a, b) => a[0] - b[0]);           // L1: O(n log n)
    const result: number[][] = [];                    // L2: O(1) setup
    for (const interval of intervals) {               // L3: O(n) iterations
        if (result.length > 0 && interval[0] <= result[result.length - 1][1]) {  // L4: O(1) check
            result[result.length - 1][1] = Math.max(result[result.length - 1][1], interval[1]);  // L5: O(1) extend
        } else {
            result.push([...interval]);               // L6: O(1) amortized
        }
    }
    return result;
}

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]  // L1: O(n log n)
    })
    result := [][]int{}                            // L2: O(1) setup
    for _, interval := range intervals {           // L3: O(n) iterations
        if len(result) > 0 && interval[0] <= result[len(result)-1][1] {  // L4: O(1) check
            if interval[1] > result[len(result)-1][1] {
                result[len(result)-1][1] = interval[1]  // L5: O(1) extend
            }
        } else {
            result = append(result, []int{interval[0], interval[1]})  // L6: O(1) amortized
        }
    }
    return result
}

final class Solution {
    func merge(_ intervals: [[Int]]) -> [[Int]] {
        let sorted = intervals.sorted { $0[0] < $1[0] }
        var result: [[Int]] = []
        for interval in sorted {
            if let last = result.last, interval[0] <= last[1] {
                result[result.count - 1][1] = max(last[1], interval[1])
            } else { result.append(interval) }
        }
        return result
    }
}

Where the time goes, line by line

Variables: n = len(intervals).

Line	Per-call cost	Times executed	Contribution
L1 (sort)	$O(n log n)$	1	$O(n log n)$ ← dominates
L2 (init)	$O(1)$	1	$O(1)$
L3 (loop)	$O(1)$	n	$O(n)$
L4 (overlap check)	$O(1)$	n	$O(n)$
L5 (extend)	$O(1)$	up to n	$O(n)$
L6 (append)	$O(1)$ amortized	up to n	$O(n)$

L1 dominates: sorting requires $O(n log n)$ comparisons, and the linear sweep that follows is $O(n)$ . Everything after the sort is a single pass.

Complexity

Time: $O(n log n)$ , driven by L1 (the sort).
Space: $O(n)$ output.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Bucket sort (when values are bounded)

If interval endpoints are bounded (e.g., within [0, 10⁴]), tally start and end events into counter arrays, then sweep tracking open intervals. Each closed run produces one merged interval.

def merge(intervals):
    if not intervals:
        return []
    max_v = max(e for _, e in intervals)
    starts = [0] * (max_v + 2)
    ends = [0] * (max_v + 2)
    for s, e in intervals:
        starts[s] += 1
        ends[e] += 1

    result = []
    open_count = 0
    cur_start = None
    for i in range(max_v + 2):
        if starts[i] > 0 and open_count == 0:
            cur_start = i
        open_count += starts[i]                # process starts before ends so touching merges
        if ends[i] > 0:
            open_count -= ends[i]
            if open_count == 0:
                result.append([cur_start, i])
    return result

function merge(intervals: number[][]): number[][] {
    if (intervals.length === 0) return [];
    const maxV = Math.max(...intervals.map(([, e]) => e));
    const starts = new Array(maxV + 2).fill(0);
    const ends = new Array(maxV + 2).fill(0);
    for (const [s, e] of intervals) {
        starts[s]++;
        ends[e]++;
    }

    const result: number[][] = [];
    let openCount = 0;
    let curStart = 0;
    for (let i = 0; i <= maxV + 1; i++) {
        if (starts[i] > 0 && openCount === 0) curStart = i;
        openCount += starts[i];               // process starts before ends so touching merges
        if (ends[i] > 0) {
            openCount -= ends[i];
            if (openCount === 0) result.push([curStart, i]);
        }
    }
    return result;
}

func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return [][]int{}
    }
    maxV := 0
    for _, iv := range intervals {
        if iv[1] > maxV { maxV = iv[1] }
    }
    starts := make([]int, maxV+2)
    ends := make([]int, maxV+2)
    for _, iv := range intervals {
        starts[iv[0]]++
        ends[iv[1]]++
    }
    result := [][]int{}
    openCount := 0
    curStart := 0
    for i := 0; i < maxV+2; i++ {
        if starts[i] > 0 && openCount == 0 { curStart = i }
        openCount += starts[i]              // process starts before ends so touching merges
        if ends[i] > 0 {
            openCount -= ends[i]
            if openCount == 0 {
                result = append(result, []int{curStart, i})
            }
        }
    }
    return result
}

final class Solution {
    func merge(_ intervals: [[Int]]) -> [[Int]] {
        let maximum = intervals.map { $0[1] }.max()!
        var starts = Array(repeating: 0, count: maximum + 2)
        var ends = Array(repeating: 0, count: maximum + 2)
        for interval in intervals { starts[interval[0]] += 1; ends[interval[1]] += 1 }
        var result: [[Int]] = []
        var open = 0
        var start = 0
        for value in 0...maximum {
            if starts[value] > 0 && open == 0 { start = value }
            open += starts[value]
            open -= ends[value]
            if ends[value] > 0 && open == 0 { result.append([start, value]) }
        }
        return result
    }
}

Rarely worth it in practice; the constant factors and the array allocation only pay off for tiny bounded ranges.

Complexity

Time: $O(max_value)$ .
Space: $O(max_value)$ .

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Quadratic pairwise	$O(n²)$	$O(n)$
Sort + linear merge	$O(n log n)$	$O(n)$
Bucket sort	$O(max_value)$	$O(max_value)$

Standard answer is sort + sweep. The same template feeds Insert Interval, Meeting Rooms II, and more.

# Quick smoke tests, paste into a REPL or save as test_056_merge_intervals.py and run.
# Uses the canonical implementation (Approach 2).

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    result = []
    for interval in intervals:
        if result and interval[0] <= result[-1][1]:
            result[-1][1] = max(result[-1][1], interval[1])
        else:
            result.append(list(interval))
    return result

def _run_tests():
    # Example 1 from problem statement
    assert merge([[1,3],[2,6],[8,10],[15,18]]) == [[1,6],[8,10],[15,18]]
    # Example 2: touching endpoints merge
    assert merge([[1,4],[4,5]]) == [[1,5]]
    # Single interval (edge case)
    assert merge([[1,2]]) == [[1,2]]
    # All overlap into one
    assert merge([[1,10],[2,5],[3,8]]) == [[1,10]]
    # Already non-overlapping
    assert merge([[1,2],[3,4],[5,6]]) == [[1,2],[3,4],[5,6]]
    # Unsorted input
    assert merge([[15,18],[1,3],[2,6],[8,10]]) == [[1,6],[8,10],[15,18]]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function merge(intervals: number[][]): number[][] {
    intervals.sort((a, b) => a[0] - b[0]);
    const result: number[][] = [];
    for (const interval of intervals) {
        if (result.length > 0 && interval[0] <= result[result.length - 1][1]) {
            result[result.length - 1][1] = Math.max(result[result.length - 1][1], interval[1]);
        } else {
            result.push([...interval]);
        }
    }
    return result;
}

console.assert(JSON.stringify(merge([[1,3],[2,6],[8,10],[15,18]])) === JSON.stringify([[1,6],[8,10],[15,18]]));
console.assert(JSON.stringify(merge([[1,4],[4,5]])) === JSON.stringify([[1,5]]));
console.assert(JSON.stringify(merge([[1,2]])) === JSON.stringify([[1,2]]));
console.assert(JSON.stringify(merge([[1,10],[2,5],[3,8]])) === JSON.stringify([[1,10]]));
console.assert(JSON.stringify(merge([[1,2],[3,4],[5,6]])) === JSON.stringify([[1,2],[3,4],[5,6]]));
console.assert(JSON.stringify(merge([[15,18],[1,3],[2,6],[8,10]])) === JSON.stringify([[1,6],[8,10],[15,18]]));
console.log("all tests pass");

Arrays, sort + sweep

Intervals, range-boundary tactics for overlap, containment, scheduling, and sweep-line problems.
Merge Intervals, sorted-boundary tactics for combining overlapping ranges and maintaining the current covered span.
Sorting as Preprocessing, order-first tactics that pay O(n log n) so adjacency, monotonic movement, or greedy choice becomes visible.

56. Merge Intervals (Medium)

Problem

Try it yourself

Approach 1: Brute force, quadratic merge

Approach 2: Sort by start + linear merge (canonical)

Approach 3: Bucket sort (when values are bounded)

Summary

Test cases

Related data structures

Related concepts