Coding Interview: How Do You Intersect Two Sorted Interval Lists?

Problem and applicable context

You receive arrays A and B. Each item is a closed interval [start, end]; both arrays are sorted by nondecreasing start, and intervals inside one array do not overlap. Return every interval covered by both lists, also ordered by start.

For A = [[1,5],[10,14]] and B = [[2,3],[4,12]], the intersections are [[2,3],[4,5],[10,12]]. Equal endpoints count, so [1,2] and [2,4] intersect at [2,2].

What the interviewer is testing

The interviewer wants to see whether you turn two sorted sequences into a monotonic two-pointer scan instead of comparing every pair. A strong answer defines closed-interval semantics, computes max(start) and min(end), and proves why only the interval with the earlier end can be discarded.

Clarifications before coding

1. Are intervals closed or half-open? This changes whether equal endpoints produce output.
2. Are both lists sorted and internally disjoint? If not, sort them or merge each list first.
3. Can input be empty, contain point intervals, or contain start > end? This determines validation.
4. Should zero-length intersections be kept? This problem keeps them because intervals are closed.

30-second answer framework

“I keep pointers i and j. The current intersection starts at the larger start and ends at the smaller end; I emit it when the left endpoint is no greater than the right endpoint. Then I advance the interval with the smaller end, because later starts cannot overlap an interval that has already ended. If the ends tie, I advance both. Each pointer moves through its list once, so the scan is O(m+n) with O(1) working space apart from output.”

Step-by-step deep dive

Step 1: Fix the interval semantics

Treat each interval as [start,end]. Let left = max(A[i].start, B[j].start) and right = min(A[i].end, B[j].end). An intersection exists when the left endpoint is no greater than the right endpoint; equal endpoints form a valid point.

Step 2: Derive pointer movement

If A[i].end is less than B[j].end, A[i] ends first. Every later interval in B starts no earlier than B[j], so A[i] cannot intersect B[j+1] or anything after it. Advance i. The case where B[j] ends first is symmetric.

Step 3: Handle equal ends

When the ends are equal, neither current interval has remaining time that can overlap a later interval. Advance both pointers. Advancing only one side rechecks an exhausted interval and can create needless comparisons or obscure the proof.

Step 4: Write an executable skeleton

function intersect(A: number[][], B: number[][]): number[][] {
  const out: number[][] = [];
  let i = 0;
  let j = 0;

  while (i < A.length && j < B.length) {
    const left = Math.max(A[i][0], B[j][0]);
    const right = Math.min(A[i][1], B[j][1]);
    if (left <= right) out.push([left, right]);

    if (A[i][1] < B[j][1]) i++;
    else if (B[j][1] < A[i][1]) j++;
    else { i++; j++; }
  }
  return out;
}

Step 5: State the invariant for correctness

At the start of each loop, i and j identify the earliest pair not yet proved unable to intersect. [left,right] is the only possible intersection of that pair, so emitting it is complete for the pair. After discarding the earlier-ending interval, every skipped pair has a later start than an interval that has already ended, so no intersection is lost.

Step 6: Analyze complexity and input defense

The pointers only advance, at most m+n times, so time is O(m+n). Working space is O(1) excluding the output, or O(k) including k emitted intervals. If sorting and valid endpoints are not guaranteed, validate or normalize first; the linear proof does not apply to arbitrary input.

High-quality sample answer

I would first confirm closed intervals, sorted starts, and no overlap within either list. For A[i] and B[j], the intersection uses the larger start and smaller end; with closed endpoints, an endpoint that is no greater than the other endpoint still emits a point. I then advance the pointer whose interval ends first, because later starts cannot overlap an interval that is already over; equal ends advance both. Each interval is processed once, giving O(m+n) time. I would test empty input, no overlap, equal endpoints, point intervals, containment, and several consecutive intersections.

Common mistakes

• Mistake → emit only when the left endpoint is strictly smaller → Why it fails: a closed interval's point intersection disappears → Fix: confirm the contract and keep equal endpoints.
• Mistake → scan every B interval for each A interval → Why it fails: sorting is ignored and time becomes O(mn) → Fix: maintain monotonic pointers.
• Mistake → always increment i → Why it fails: B[j] may end first, causing repeated comparisons or missed output → Fix: compare ends and advance the smaller one, both on a tie.
• Mistake → claim linear time without sorted input → Why it fails: the pointer proof no longer holds → Fix: sort or merge each list first.

Follow-up questions and responses

What changes for half-open intervals [start,end)?

Require the left endpoint to be strictly smaller; [1,2) and [2,4) have no point intersection. The end comparison for pointer movement can stay the same, but state the endpoint contract explicitly.

Can you keep O(m+n) if each list is unsorted and overlapping?

Not directly. Sort and merge each list first, which costs at least O(m log m+n log n), then run the linear two-pointer scan.

What if the output should be total intersection length?

Keep the scan and accumulate each right-left, adjusted for the endpoint convention. For integer closed intervals, clarify whether length means geometric span or number of included points before writing the formula.

What if the two lists are streams that cannot be rewound?

As long as each stream remains start-sorted, retain the current interval and next-read position as the pointer state. After emitting an intersection, discard the interval that ended; out-of-order data requires buffering and a different design.