Skip to content

161 — Merge Intervals

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

161 — Merge Intervals

LeetCode 56 · Medium. 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.

🍽️ Intuition

Imagine a pile of sticky notes, each with a time range scrawled on it, tossed onto your desk in random order. Two notes "belong together" if their ranges touch or cross at all. Comparing every note against every other note to find these groups is exhausting and repetitive. But if you first line the notes up left to right by their start time, something nice happens: any two notes that overlap must end up next to each other in that lineup — there's no way for two overlapping ranges to have a bunch of other ranges sandwiched between them once everything is sorted by start. That collapses the problem to a single walk down the line, gluing each note onto the open one in your hand until a gap forces you to set it down and pick up a fresh one.

🚩 Pattern-Recognition Cue

"Merge all overlapping intervals", applied to an unsorted list of [start, end] ranges, is the archetypal Merge Intervals signature — the moment you see "merge" plus "overlapping" plus a list of ranges with no ordering guarantee, sorting by start time first turns an all-pairs comparison into one linear sweep.

🐢 Brute Force

Repeatedly scan the current list for any pair of overlapping intervals, splice that pair into one merged interval, and start over — keep doing full passes until an entire pass finds nothing left to merge.

func mergeBruteForce(_ intervals: [[Int]]) -> [[Int]] {
    var result = intervals
    var didMerge = true

    while didMerge {
        didMerge = false

        mergePass: for i in 0..<result.count {
            for j in (i + 1)..<result.count {
                let a = result[i]
                let b = result[j]
                if a[0] <= b[1] && b[0] <= a[1] {
                    let combined = [min(a[0], b[0]), max(a[1], b[1])]
                    result.remove(at: j)
                    result.remove(at: i)
                    result.append(combined)
                    didMerge = true
                    break mergePass
                }
            }
        }
    }

    return result.sorted { $0[0] < $1[0] }
}

// smoke test
print(mergeBruteForce([[1,3],[2,6],[8,10],[15,18]]))   // [[1,6],[8,10],[15,18]]
print(mergeBruteForce([[1,4],[4,5]]))                  // [[1,5]]
print(mergeBruteForce([]))                             // []
print(mergeBruteForce([[1,4]]))                        // [[1,4]]

Big-O: O(n^3) time worst case — up to n merge passes, each scanning up to O(n^2) pairs looking for the next overlap. O(n) space.

🚀 Optimal

Sort once by start time, then sweep once: keep exactly one "current block" (the last entry of result), and either stretch its end to absorb the next interval or close it out and open a new block.

func merge(_ intervals: [[Int]]) -> [[Int]] {
    guard !intervals.isEmpty else { return [] }

    let sorted = intervals.sorted { $0[0] < $1[0] }
    var result: [[Int]] = [sorted[0]]

    for interval in sorted.dropFirst() {
        let lastIndex = result.count - 1
        if interval[0] <= result[lastIndex][1] {
            result[lastIndex][1] = max(result[lastIndex][1], interval[1])
        } else {
            result.append(interval)
        }
    }

    return result
}

// smoke test — same cases as the brute force
print(merge([[1,3],[2,6],[8,10],[15,18]]))   // [[1,6],[8,10],[15,18]]
print(merge([[1,4],[4,5]]))                  // [[1,5]]
print(merge([]))                             // []
print(merge([[1,4]]))                        // [[1,4]]

Big-O: O(n log n) time — one sort, then a single linear sweep. O(n) space for the result (plus whatever the sort implementation uses internally).

🔑 The Key Insight

The brute force keeps re-scanning the entire list after every single merge because it has no guarantee about where the next overlapping pair might be hiding — they could be anywhere. Sorting by start time removes that uncertainty entirely: once sorted, any interval that's going to overlap the block you're currently building can only be the very next one in line, never some interval further down the list first colliding with something in between. That's what turns "repeatedly search the whole list" into "look at exactly one interval per step," dropping the algorithm from cubic time down to the cost of the sort itself.

🔗 Related Chapters

  • Merge Intervals — this problem is the pattern chapter's own worked example: sort by start, sweep once, stretch or open a new block.
  • Arrays and Strings — both versions operate on a plain array of [start, end] pairs, building the merged result into a second array.

🧸 Memory Sentence

Merge Intervals is the sticky-note lineup — sort by start time, then sweep once, stretching the current block until a gap forces a new one.

✅ Check Your Understanding

  1. Why does sorting by start time guarantee that any interval overlapping the current block must appear immediately next in the sorted order, rather than somewhere further down the list?
  2. The overlap check uses interval[0] <= result[lastIndex][1] (less-than-or-equal). What would go wrong on the input [[1,4],[4,5]] if this were strict < instead?
  3. Why does the brute force's outer while didMerge loop need to restart the entire double loop from scratch after every single merge, instead of just continuing where it left off?
  4. What does merge([]) return, and why does the optimal version need an explicit guard for it while the brute force's while loop handles it without one?

⬅️ Previous: Insert Interval · Next: Non-overlapping Intervals ➡️

Clone this wiki locally