You are given two lists of closed intervals, firstList and secondList, where each list[i] = [start_i, end_i]. Each list is pairwise disjoint and sorted in ascending order by start.
Return the intersection of the two interval lists: the list of closed intervals covered by both inputs, sorted by start. The intersection of two closed intervals [a, b] and [c, d] is [max(a, c), min(b, d)] — and it exists only when max(a, c) <= min(b, d) (touching endpoints count, so an intersection can be a single point like [5, 5]).
Example
Each output interval is covered by one interval from each list; e.g. [5,10] ∩ [1,5] = [5,5].
Constraints
- 0 <= firstList.length, secondList.length <= 1000
- firstList.length + secondList.length >= 1
- 0 <= start_i <= end_i <= 10^9
- Each list is pairwise disjoint and sorted by start.
Intuition
The intersections are the ranges covered by both lists, so a first pass simply tests every interval from the first list against every interval from the second, recording any overlap it finds.
function intervalIntersection(firstList, secondList) {
const result = [];
// Compare each interval in A against each interval in B.
for (const [aStart, aEnd] of firstList) {
for (const [bStart, bEnd] of secondList) {
// The overlap of two closed intervals is [max start, min end].
const lo = Math.max(aStart, bStart);
const hi = Math.min(aEnd, bEnd);
if (lo <= hi) result.push([lo, hi]); // non-empty → it's a real intersection
}
}
return result.sort((a, b) => a[0] - b[0]); // present in start order
}Checking every pair is O(m × n), and it ignores a gift the input already hands us: both lists are sorted by start. Can we do better?
Because the lists are sorted, we can sweep them together with one pointer each — the same two-pointer merge posture as combining two sorted arrays. At each step the only candidate intersection is between the current interval of each list: [max(starts), min(ends)], emitted when that range is non-empty.
Then comes the one insight that makes it linear: advance the pointer of whichever interval ends first. That interval can't possibly intersect anything later in the other list (everything there starts even further right), while the one that ends later might still meet the other list's next interval — so it stays put.
Walking it through:
list A (pointer i) — A = [[0,2], [5,10], [13,23]]
Step 1: overlap of [0,2] and [1,5] is [max(0,1), min(2,5)] = [1,2]. A ends sooner, so advance i.
Step 2: [5,10] meets [1,5] at the single point 5. B ends sooner now, so j advances (i stays).
Step 3: [5,10] and [8,12] overlap on [8,10]. A ends sooner, so advance i.
Step 4: [13,23] sits past B's frontier; nothing left intersects. Collected: [[1,2], [5,5], [8,10]].
list B (pointer j) — B = [[1,5], [8,12], [15,24]] — same four steps, B's side
B's [1,5] ends at 5, later than A's [0,2] (ends 2), so j holds while i advances.
After A moves to [5,10], B's [1,5] is the one that ends first (5 < 10), so j finally advances.
[8,12] ends at 12, past A's [5,10] (ends 10), so j holds while i advances again.
With A's pointer off the end, the loop stops — B's remaining intervals can't intersect anything.
Reading the two lanes: they show the same four steps from each list's side — pointer i over A on top, j over B below. A single lane can't draw the cross-list comparison, so the decision lives in each step's action: the candidate overlap [max(starts), min(ends)] and the rule that whichever interval ends first advances. Each pointer only ever moves forward, so the whole sweep is linear in the two lengths.
Optimization
Two-pointer sweep
Both lists are already sorted by start, so sweep them together with one pointer each. For the current pair of intervals, the candidate intersection is [max(starts), min(ends)]; emit it when max(starts) <= min(ends). Then advance the pointer of whichever interval ends first — it can't intersect anything later in the other list, while the one that ends later might still meet the other list's next interval.
O(m + n) time (each pointer advances at most its list's length), O(1) extra space beyond the output.
function intervalIntersection(firstList, secondList) {
const result = [];
let i = 0;
let j = 0;
// Sweep both sorted lists with one pointer each.
while (i < firstList.length && j < secondList.length) {
const [aStart, aEnd] = firstList[i];
const [bStart, bEnd] = secondList[j];
// Overlap of two closed intervals: [max start, min end].
const lo = Math.max(aStart, bStart);
const hi = Math.min(aEnd, bEnd);
if (lo <= hi) result.push([lo, hi]);
// Drop whichever interval ends first; it can't reach further right.
if (aEnd < bEnd) i++;
else j++;
}
return result;
}Complexity analysis
Time complexity: O(m + n). Here's why:
- Each step of the sweep advances exactly one of the two pointers.
- A pointer only ever moves forward and stops at the end of its list, so the total number of steps is at most
m + n.
No sorting is needed — the inputs arrive sorted — so the whole sweep is O(m + n), where m and n are the two list lengths.
Space complexity: O(1). Here's why:
- The sweep keeps only the two pointers and a handful of scalars.
That's O(1) auxiliary space. The result list isn't counted; it can hold up to O(m + n) intersection intervals in the worst case.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| firstList = [], secondList = [] | [] | Both lists empty — no intersections. |
| firstList = 13 | [] | One list empty — nothing to intersect against. |
| firstList = 12 34 | [] | Disjoint single intervals — no overlap. |
| firstList = 26 610 | [[6,6]] | Touching at one point yields the single-point intersection [6,6]. |
| firstList = 110 23 45 | [[2,3],[4,5]] | One interval fully contains two from the other list. |
| firstList = 04 711 38 | [[3,4],[7,8]] | One B interval spans the gap, overlapping both A intervals. |
Try it yourself
Write your solution against the real judge before checking the reference.