Interval List Intersections
You are given two lists of closed intervals, firstList and secondList, where firstListi = [starti, endi] and secondListj = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order . Return the intersection of these two interval lists. A closed interval [a, b] (with a ≤ b) denotes the set of real numbers x with a ≤ x ≤ b. The intersection of two closed intervals is a set of real numbers that is either empty or can be represented as a closed interval. Use one pointer per list: compute the overlap of the current pair , and advance whichever interval ends first.
Constraints
- 0 ≤ firstList.length, secondList.length ≤ 1000
- firstList.length + secondList.length ≥ 1
- 0 ≤ starti < endi ≤ 109
- endi < starti+1
- 0 ≤ startj < endj ≤ 109
- endj < startj+1
Example
firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]][[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]Explanation Each pair of overlapping intervals contributes its overlap — the later of the two starts to the earlier of the two ends — to the result.
In plain terms
- Interval
- A closed range of numbers written [a, b], meaning every number from a to b, including both endpoints — like saying "from 3 to 7" and meaning 3, 7, and everything between.
- Disjoint
- Intervals in the same list never overlap each other — each one ends before the next one begins.
One pointer per list, advancing whichever interval ends first
i=0 ([0,2]), j=0 ([1,5]): overlap = [max(0,1), min(2,5)] = [1,2] — record it. firstList[i] ends first (2 < 5), advance i.
What happens in this step
i=0 → [0,2] j=0 → [1,5] start = max(0, 1) = 1 end = min(2, 5) = 2 1 <= 2 → valid, record [1, 2] firstList[i][1]=2 < secondList[j][1]=5, so i advances (i → 1) since the shorter-reaching interval can't overlap anything further ahead.
Steps to visualize
- Point i at the first interval of firstList and j at the first interval of secondList.
- Compute the overlap: the later of the two starts to the earlier of the two ends.
- If the overlap is valid (start ≤ end), record it.
- Advance whichever interval ends first, since it cannot overlap with anything further ahead in the other list.
- Stop once either list is exhausted.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
i=0 ([0,2]), j=0 ([1,5]): overlap = [max(0,1), min(2,5)] = [1,2] — record it. firstList[i] ends first (2 < 5), advance i.
What happens in this step
i=0 → [0,2] j=0 → [1,5] start = max(0, 1) = 1 end = min(2, 5) = 2 1 <= 2 → valid, record [1, 2] firstList[i][1]=2 < secondList[j][1]=5, so i advances (i → 1) since the shorter-reaching interval can't overlap anything further ahead.
Solution
function intervalIntersection(firstList, secondList) {
const result = [];
let i = 0;
let j = 0;
while (i < firstList.length && j < secondList.length) {
const start = Math.max(firstList[i][0], secondList[j][0]);
const end = Math.min(firstList[i][1], secondList[j][1]);
if (start <= end) {
result.push([start, end]);
}
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
}
return result;
}- Time
- O(m + n)
- Space
- O(1) (excluding the output array)
Test cases
| Input | Expected | Covers |
|---|---|---|
firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] | [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] | example from the docstring |
firstList = [[1,2]], secondList = [[3,4]] | [] | no overlap at all between the two lists |
firstList = [], secondList = [[1,3]] | [] | one list is empty, so there can be no intersection |
firstList = [[1,3],[5,7]], secondList = [[1,3],[5,7]] | [[1,3],[5,7]] | two identical lists intersect with themselves entirely |
firstList = [[1,5]], secondList = [[5,10]] | [[5,5]] | intervals that touch at exactly a single point |
firstList = [[2,6]], secondList = [[1,10]] | [[2,6]] | one interval fully nested inside the other |