986. Interval List Intersections

At a Glance

Topic: intervals
Pattern: Two Pointers on sorted interval lists
Difficulty: Medium
Companies: Google, Uber, Facebook, Amazon, Apple
Frequency: High
LeetCode: 986

Given two lists of sorted, disjoint intervals firstList and secondList, return all non-empty intersections between any pair (one from each list). Input: two lists. Output: list of intersection intervals.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Two sorted sequences → two pointers
Intersection of [a,b] and [c,d] is [max(a,c), min(b,d)] if max(a,c) <= min(b,d)
Advance pointer whose interval ends first

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Check all pairs — O(n*m) time.
Two pointers — O(n+m) time / O(1) extra beyond output. <- pick this in interview.

Optimal Solution

Go

package main

func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
	firstIndex := 0
	secondIndex := 0
	result := make([][]int, 0)
	for firstIndex < len(firstList) && secondIndex < len(secondList) {
		firstStart := firstList[firstIndex][0]
		firstEnd := firstList[firstIndex][1]
		secondStart := secondList[secondIndex][0]
		secondEnd := secondList[secondIndex][1]
		overlapStart := firstStart
		if secondStart > overlapStart {
			overlapStart = secondStart
		}
		overlapEnd := firstEnd
		if secondEnd < overlapEnd {
			overlapEnd = secondEnd
		}
		if overlapStart <= overlapEnd {
			result = append(result, []int{overlapStart, overlapEnd})
		}
		if firstEnd < secondEnd {
			firstIndex++
		} else {
			secondIndex++
		}
	}
	return result
}

JavaScript

function intervalIntersection(firstList, secondList) {
	let firstIndex = 0;
	let secondIndex = 0;
	const result = [];
	while (firstIndex < firstList.length && secondIndex < secondList.length) {
		const [firstStart, firstEnd] = firstList[firstIndex];
		const [secondStart, secondEnd] = secondList[secondIndex];
		const overlapStart = Math.max(firstStart, secondStart);
		const overlapEnd = Math.min(firstEnd, secondEnd);
		if (overlapStart <= overlapEnd) {
			result.push([overlapStart, overlapEnd]);
		}
		if (firstEnd < secondEnd) {
			firstIndex++;
		} else {
			secondIndex++;
		}
	}
	return result;
}