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.

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

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;
}