Interval Intersections LeetCode 986 Guide

LeetCode 986, Interval List Intersections, gives you two sorted lists of disjoint, closed intervals — firstList and secondList — and asks you to return the intersection of these two lists. An interval [a, b] intersects [c, d] if and only if they share at least one point; the intersection is [max(a,c), min(b,d)] whenever that start does not exceed that end.

Both input lists are already sorted in ascending order and each list contains only disjoint intervals (no two intervals within the same list overlap). This structure is what makes a two-pointer approach natural: you never need to backtrack, and you can process both lists in a single left-to-right pass.

The problem is classified as Medium and is a direct member of the interval two-pointer family alongside Merge Intervals and Meeting Rooms. Understanding the overlap condition and the pointer-advance rule is the entire solution — once you see those two ideas clearly, the code is only about ten lines.

Use pointer i for firstList and pointer j for secondList, both starting at 0. At each step, you consider the current pair A[i] and B[j]. Compute whether they overlap, and if so record the intersection. Then advance the pointer whose interval ends first — that interval cannot contribute any further overlaps because the other pointer has not yet passed its end.

The key insight is that because both lists are sorted and disjoint, the interval that ends sooner among A[i] and B[j] can never overlap with any future interval from its own list (since future intervals start later than its end). The interval that ends later, however, might still overlap with the next interval from the other list — so we keep it in place and only advance the shorter one.

This greedy pointer-advance rule is the heart of the algorithm. It guarantees that every pair of intervals is considered at most once, giving O(m+n) total iterations where m = len(firstList) and n = len(secondList). The loop terminates when either pointer exhausts its list.

For the current pair A[i] = [startA, endA] and B[j] = [startB, endB], the potential intersection starts at intersectionStart = max(startA, startB) and ends at intersectionEnd = min(endA, endB). If intersectionStart <= intersectionEnd, the intervals actually overlap and [intersectionStart, intersectionEnd] is a valid intersection interval to add to the result.

If intersectionStart > intersectionEnd, the intervals do not overlap — one ends before the other begins — and you produce no output for this pair. You still advance the pointer whose interval ends sooner and continue to the next pair.

Because the input intervals are closed (both endpoints are included), a single shared point counts as an intersection. For example [1, 2] and [2, 3] intersect at [2, 2]. The condition max(start) <= min(end) correctly captures this: 2 <= 2 is true, and the intersection [2, 2] is valid.

After processing the current pair, advance the pointer whose interval ends first. If endA < endB, increment i (move to the next interval in firstList). Otherwise increment j (move to the next interval in secondList). When endA == endB, it does not matter which you advance — both intervals end at the same point so neither can overlap with anything the other has not yet seen.

This rule is correct because an interval that ends before the other cannot overlap with any future interval from the other list — those future intervals start at or after the current interval in the other list ends, which is already past the end of the interval we are discarding. The interval that ends later, however, might reach into the next interval from the other list.

A common mistake is to advance both pointers when the current pair overlaps. Do not do this. Only advance the pointer whose interval ends sooner. The longer interval may still overlap with one or more subsequent intervals from the other list, and advancing both would skip those intersections.

Consider A = [[0,2],[5,10],[13,23],[24,25]] and B = [[1,5],[8,12],[15,24],[25,26]]. Start with i=0, j=0. A[0]=[0,2] and B[0]=[1,5]: intersection = [max(0,1), min(2,5)] = [1,2]. Since endA=2 < endB=5, advance i to 1.

Now i=1, j=0. A[1]=[5,10] and B[0]=[1,5]: intersection = [max(5,1), min(10,5)] = [5,5]. Since endA=10 > endB=5, advance j to 1. Now i=1, j=1. A[1]=[5,10] and B[1]=[8,12]: intersection = [8,10]. Since endA=10 < endB=12, advance i to 2.

Continue: i=2, j=1. A[2]=[13,23] vs B[1]=[8,12]: max(13,8)=13, min(23,12)=12 — no overlap (13 > 12), advance j (endB=12 < endA=23) to 2. i=2, j=2: A[2]=[13,23] vs B[2]=[15,24]: intersection = [15,23], advance i. i=3, j=2: A[3]=[24,25] vs B[2]=[15,24]: intersection = [24,24], advance j. i=3, j=3: A[3]=[24,25] vs B[3]=[25,26]: intersection = [25,25]. Result: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].

Python: def intervalIntersection(A, B): i = j = 0; result = []; while i < len(A) and j < len(B): lo = max(A[i][0], B[j][0]); hi = min(A[i][1], B[j][1]); if lo <= hi: result.append([lo, hi]); if A[i][1] < B[j][1]: i += 1; else: j += 1; return result. Time complexity O(m+n), space O(1) extra (the result list does not count as extra space).

Java: List<int[]> res = new ArrayList<>(); int i = 0, j = 0; while (i < A.length && j < B.length) { int lo = Math.max(A[i][0], B[j][0]); int hi = Math.min(A[i][1], B[j][1]); if (lo <= hi) res.add(new int[]{lo, hi}); if (A[i][1] < B[j][1]) i++; else j++; } return res.toArray(new int[0][]). Both implementations are compact and run in O(m+n) time with O(1) auxiliary space.

The while loop terminates as soon as either pointer reaches the end of its list, because no further intersections can exist once one list is exhausted. The result list can contain at most m+n intervals in the worst case (when every interval in one list overlaps with exactly one interval in the other), so output space is O(m+n) but this is not counted as "extra" space since it is the required output.

Interval List Intersections is part of the interval two-pointer family. Merge Intervals (LeetCode 56) handles a single unsorted list and requires sorting first, then a greedy merge pass. Meeting Rooms II (LeetCode 253) uses a min-heap or two-pointer on sorted start and end times to count the minimum number of rooms needed — a different application of the same sorted-interval scan idea.

Non-Overlapping Intervals (LeetCode 435) asks for the minimum number of intervals to remove so that no two remaining intervals overlap; this is equivalent to maximizing the number of non-overlapping intervals, solved greedily by always keeping the interval with the earliest end time. Insert Interval (LeetCode 57) handles inserting a new interval into an already-sorted, disjoint list and merging any resulting overlaps in O(n) time.

The unifying theme across all interval problems is the overlap condition max(start) <= min(end) and the importance of sorting by start time (or leveraging already-sorted input). Mastering interval intersections gives you the two-pointer pattern that appears in Meeting Rooms, Employee Free Time (LeetCode 759), and any problem involving pairwise overlap detection across two sorted sequences.