Intervals crash course ↗ · 108

56. Merge Intervals

Sort the intervals by start value first — that single step guarantees any overlap only happens with the immediately preceding merged interval, enabling a clean O(n) sweep instead of an O(n²) nested comparison.

● MediumSortingIntervalsTypeScript

PROBLEM What we're solving

Given an array of intervals [[start, end], …], merge all overlapping intervals and return the result. Two intervals overlap when one starts at or before the other ends.

Example: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]] because [1,3] and [2,6]overlap (2 ≤ 3), so they fuse into [1,6]. The remaining two pairs have gaps, so they stay separate.

KEY IDEA Sorting by start collapses the problem to a single sweep

Insight → If you sort by start value first, then every interval can only overlap with the interval that was most recently added to the result list — never an earlier one. So you only need to compare current.start against last.end. One forward pass, no backtracking.

RECIPE Sort, sweep, extend-or-push

1 · Sort by start. intervals.sort((a, b) => a[0] - b[0]). This is the enabling step — overlaps become local (adjacent).
2 · Init result. Push the first sorted interval directly; it has nothing to overlap with yet.
3 · Sweep. For each subsequent interval [start, end]:
- If start <= last.end — overlap: update last.end = max(last.end, end). Use maxbecause a fully-contained interval wouldn't extend the end.
- Otherwise — gap: push [start, end] as a new entry.
4 · Return the result array.

Classic confusion → forgetting Math.max when extending. If the new interval is fully contained within the last merged one (e.g. [1,10] followed by [2,5]), a naive last.end = end would incorrectly shrink the result to [1,5].

COST Complexity & alternatives

Brute force (nested loops)

O(n²)

Compare every pair; no sort needed but very slow.

Sort + sweep

O(n log n)

Dominated by sort; O(n) extra space for output.

The sweep itself is O(n) — each interval is pushed or merged exactly once. Total is O(n log n) for the sort. In-place mutation of the input is possible but messy; the idiomatic approach uses a separate output array.

Pattern transfer → the same sort-then-sweep skeleton applies to Insert Interval (LC 57), Non-overlapping Intervals(LC 435), and Meeting Rooms I&II — sort events by start and process them in order.

RUN IT Sort by start, then sweep and merge

intervals (a-b pairs separated by ;)

step 0 / 6

STARTInput: [1,3], [2,6], [8,10], [15,18]. First we sort by start value — that is the key step that makes a single sweep possible.

1▶function merge(intervals: number[][]): number[][] {
2  // Sort by start so any overlap must be with the immediately previous merged interval
3  intervals.sort((a, b) => a[0] - b[0]);
4 
5▶  const merged: number[][] = [];
6 
7  for (const [start, end] of intervals) {
8    if (merged.length === 0) {
9      merged.push([start, end]);
10      continue;
11    }
12 
13    const last = merged[merged.length - 1];
14 
15    if (start <= last[1]) {
16      // Overlapping: extend the end if needed
17      last[1] = Math.max(last[1], end);
18    } else {
19      // Gap: start a fresh interval
20      merged.push([start, end]);
21    }
22  }
23 
24  return merged;
25}

input (unsorted)1-302-618-10215-183

State

[]

merged

[]

result

sort

phase

current intervalmerged resultoverlap detectednot yet processed

slowfast

TYPESCRIPT The solution, annotated

mergeIntervals.ts
function merge(intervals: number[][]): number[][] {
  // Sort by start so any overlap must be with the immediately previous merged interval
  intervals.sort((a, b) => a[0] - b[0]);

  const merged: number[][] = [];

  for (const [start, end] of intervals) {
    if (merged.length === 0) {
      merged.push([start, end]);
      continue;
    }

    const last = merged[merged.length - 1];

    if (start <= last[1]) {
      // Overlapping: extend the end if needed
      last[1] = Math.max(last[1], end);
    } else {
      // Gap: start a fresh interval
      merged.push([start, end]);
    }
  }

  return merged;
}

Reading it block by block

Line 3 — sort by start. This is the entire trick: after sorting, any interval that overlaps [start, end]must be the one immediately before it in the sorted list. A later interval can't start earlier, so it can't retroactively extend an already-closed gap.

Lines 7–10 — first interval. The result list is empty, so push [start, end] unconditionally and continue to the next.

Lines 12–13 — peek at the last merged interval. We only need the tail of the result; earlier entries are final and will never change again (because sort guarantees no future interval starts before the current one).

Lines 15–17 — overlap branch. start <= last[1] means the current interval begins inside or at the boundary of the last merged one. Extend the end with Math.max(last[1], end) — the max handles full containment (e.g. [1,10] swallowing [2,5]).

Lines 18–20 — gap branch. start > last[1]means there's a real gap. The previous merged interval is now closed forever; push a fresh one.

Line 24 — return.Every interval has been processed exactly once: O(n) sweep after an O(n log n) sort.

Complexity → O(n log n) time (dominated by sort), O(n) space for the output array. The sweep itself is O(n) — each interval enters and leaves the "last merged" slot at most once.

INTERVIEWFollow-ups they'll ask

"What if intervals can have negative starts?" No change — the sort comparator works for all integers.
"Can you do it in-place?" Yes: overwrite the input array with merged intervals using a write pointer. Saves a separate array but complicates the code and is rarely worth it.
"Insert Interval next?" A twist: one new interval arrives and must be merged into an already-sorted list. Split into three phases: copy left (no overlap), merge middle (overlap), copy right.
"Non-overlapping Intervals (min removals)?" Sort by end, greedily keep the interval with the earliest end — classic greedy scheduling. The sort step is the same key move.
"Meeting Rooms II (min rooms)?" Split into start/end event arrays, sort both, sweep with two pointers or a min-heap to track concurrent meetings.

OPTIMAL Sorting

mergeIntervals.ts
function merge(intervals: number[][]): number[][] {
  // Sort by start so any overlap must be with the immediately previous merged interval
  intervals.sort((a, b) => a[0] - b[0]);

  const merged: number[][] = [];

  for (const [start, end] of intervals) {
    if (merged.length === 0) {
      merged.push([start, end]);
      continue;
    }

    const last = merged[merged.length - 1];

    if (start <= last[1]) {
      // Overlapping: extend the end if needed
      last[1] = Math.max(last[1], end);
    } else {
      // Gap: start a fresh interval
      merged.push([start, end]);
    }
  }

  return merged;
}

Complexity → O(n log n) time (dominated by sort), O(n) space for the output array. The sweep itself is O(n) — each interval enters and leaves the "last merged" slot at most once.

ALT 1 Brute force — repeatedly fuse any overlapping pair

O(n³) time · O(n) space

No sorting: keep scanning the list for any two intervals that overlap, merge them into one, and restart — repeat until a full pass finds nothing left to combine.

approach-2.ts
function merge(intervals: number[][]): number[][] {
  // Work on a copy so we do not mutate the caller's array.
  let result = intervals.map(([s, e]) => [s, e]);

  let merged = true;
  while (merged) {
    merged = false;

    outer: for (let i = 0; i < result.length; i++) {
      for (let j = i + 1; j < result.length; j++) {
        const [s1, e1] = result[i];
        const [s2, e2] = result[j];
        // Overlap iff each starts no later than the other ends.
        if (s1 <= e2 && s2 <= e1) {
          // Fuse j into i, then drop j and rescan from scratch.
          result[i] = [Math.min(s1, s2), Math.max(e1, e2)];
          result.splice(j, 1);
          merged = true;
          break outer;
        }
      }
    }
  }

  return result;
}

Note → Each fuse triggers a fresh O(n²) scan and there can be O(n) fuses, so this is cubic in the worst case. Sorting by start time first guarantees overlaps are adjacent, collapsing it to a single O(n log n) pass.

MNEMONIC The one-liner

"Sort starts, sweep once: overlap → stretch the end; gap → push fresh."

TRIGGERS When you see _ → reach for _

"merge overlapping intervals"	sort by start → sweep last.end
start ≤ last end	overlap: extend last[1] = max(last[1], end)
start > last end	gap: push new interval
"insert/remove/count intervals"	same sort-by-start skeleton

SKELETON The reusable shape

skeleton.ts
function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);   // sort by start
  const merged: number[][] = [];

  for (const [start, end] of intervals) {
    const last = merged[merged.length - 1];
    if (!last || start > last[1]) {
      merged.push([start, end]);            // no overlap: new interval
    } else {
      last[1] = Math.max(last[1], end);     // overlap: extend end
    }
  }

  return merged;
}

FLASHCARDS Tap to flip

Why sort by start before merging?

It makes overlaps local: any overlapping interval must be adjacent in sorted order, enabling a single O(n) sweep.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the sort-then-sweep merge algorithm?

QUESTION 02

After sorting, you compare current.start against last.end. What does current.start <= last.end mean?

QUESTION 03

You have merged [1,10] and the next sorted interval is [3,5]. What should the merged list contain after processing [3,5]?

QUESTION 04

Why is sorting by start the critical enabling step?

QUESTION 05

Input: [[1,4],[4,5]]. What is the output?

QUESTION 06

Which of these is NOT a problem that directly reuses the sort-by-start sweep pattern?

QUESTION 07

Space complexity of the standard merge-intervals solution (separate output array)?

QUESTION 08

#56 · Merge IntervalsSort the intervals by start value first — that single step guarantees any overlap only happens with the immediately preceding merged interval, enabling a clean O(n) sweep instead of an O(n²) nested comparison.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Sorting by start collapses the problem to a single sweep

RECIPE Sort, sweep, extend-or-push

COST Complexity & alternatives

RUN IT Sort by start, then sweep and merge

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Sorting

ALT 1 Brute force — repeatedly fuse any overlapping pair

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _