Topic: Learning notes

Merge Intervals in TypeScript: Build a Provable Invariant

Derive a TypeScript merge-intervals solution through sorting, one linear scan, input immutability, and an honest O(n log n) complexity analysis.

I completed this solution with AI assistance, but I did not want to keep only a piece of code that happened to run. I went back to verify why each comparison is sufficient, whether the input stays unchanged, and why sorting dominates the complexity. The durable interview skill is not memorizing the loop; it is explaining the invariant that makes one scan correct.

Problem

Given a collection of [start, end] intervals in arbitrary order, merge every pair that overlaps or touches at an endpoint. The function must not mutate its input.

For example:

[[1, 3], [2, 6], [8, 10], [10, 12]]
→ [[1, 6], [8, 12]]

Sort first, then compare only the final interval

Without ordering, a new interval could overlap any interval already seen. After sorting by ascending start, the merged output maintains two properties after every iteration:

1. Its intervals are ordered by their starts.
2. They are disjoint and already represent the complete merge of every interval processed so far.

Only the final merged interval can therefore overlap the current one. If currentStart <= lastEnd, the intervals overlap or touch, so the new end is their maximum end. If currentStart > lastEnd, all later starts are at least as large, and the current interval cannot overlap any earlier result.

That is the invariant. “We compared the earlier intervals already” is not enough by itself; sorting and fully merging the prefix are what make the last interval the only possible candidate.

TypeScript solution

type Interval = readonly [start: number, end: number];

function mergeIntervals(intervals: readonly Interval[]): Interval[] {
  if (intervals.length === 0) return [];

  const sorted = [...intervals].sort(([a], [b]) => a - b);
  const merged: Interval[] = [sorted[0]];

  for (let index = 1; index < sorted.length; index += 1) {
    const current = sorted[index];
    const lastIndex = merged.length - 1;
    const last = merged[lastIndex];

    if (current[0] <= last[1]) {
      merged[lastIndex] = [last[0], Math.max(last[1], current[1])];
    } else {
      merged.push(current);
    }
  }

  return merged;
}

sort() mutates its array, so [...intervals] first copies the outer array. A readonly tuple also prevents this function from overwriting endpoints supplied by its caller. Merging creates a new tuple instead of modifying an existing interval.

Minimal verification

console.log() leaves correctness to visual inspection. An assertion fails immediately when the result is wrong.

import assert from "node:assert/strict";

const input: Interval[] = [[1, 3], [2, 6], [8, 10], [10, 12]];
const snapshot = input.map((interval) => [...interval]);

assert.deepStrictEqual(mergeIntervals(input), [[1, 6], [8, 12]]);
assert.deepStrictEqual(input, snapshot);
assert.deepStrictEqual(mergeIntervals([]), []);
assert.deepStrictEqual(mergeIntervals([[1, 4], [2, 3]]), [[1, 4]]);

The last case matters: assigning current[1] directly would incorrectly shrink [1, 4] to [1, 3], which is why the merge uses Math.max().

Complexity and the JavaScript reality

The usual interview model treats comparison sorting as O(n log n). The subsequent scan is O(n), so the total is O(n log n) time with O(n) additional space. It is not O(n²): complexity must be derived from the operations, not guessed from the number of lines or the presence of a library call.

More precisely, ECMAScript does not guarantee the time or space complexity of Array.prototype.sort(); MDN states that both depend on the JavaScript engine. O(n log n) is the conventional model for this interview answer, not a language-level guarantee.

Common traps

• Calling sort() directly on the input and violating the immutability requirement.
• Using < instead of <= when touching endpoints must also merge.
• Replacing the last end without Math.max() and accidentally shrinking a containing interval.
• Presenting code without being able to state the sorted-prefix invariant.
• Treating function calls or logs as tests without asserting expected results.

What I learned

• Sorting matters because it reduces the possible overlap candidate to the final merged interval.
• Complexity should be calculated for sorting and scanning separately, then reduced to the dominant term.
• readonly types and an explicit copy turn “do not mutate the input” into a reviewable contract.
• AI can help produce a starting point, but I still need to verify invariants, edge cases, and complexity myself.

External references

• MDN: Array.prototype.sort(): confirms in-place mutation and implementation-dependent complexity.
• TypeScript Handbook: readonly tuple types: models interval endpoints that callers should not mutate.
• Node.js: assert.deepStrictEqual(): provides executable equality checks for the output and the original input.