LeetCode #986 Medium

Interval List Intersections

Return intersections between two sorted lists of pairwise-disjoint closed intervals.

arraytwo-pointersinterval

02

Intuition

Comparing every interval in one list with every interval in the other wastes their sorted, disjoint structure. For the current pair, any overlap is determined by the later start and earlier end. After that comparison, the interval ending first cannot overlap any later interval across the other list. Advancing that pointer yields a linear merge-style scan.

How to spot this pattern

Two sorted, internally disjoint interval lists invite a two-pointer merge. After processing a pair, the earlier-ending interval is permanently exhausted relative to all future intervals.

03

Approach

1

Compare one interval from each list

Use pointers i and j. Compute start = max(first[i].start, second[j].start) and end = min(first[i].end, second[j].end) for the only possible overlap between the current intervals.

2

Emit closed-boundary intersections

Append [start, end] when start <= end. Equality is included because these are closed intervals and a shared endpoint is a valid one-point intersection.

3

Discard the interval that finishes first

Advance i when the first interval's end is smaller; otherwise advance j. If ends are equal, advancing either is safe because neither interval can overlap a future interval from the opposite disjoint list.

04

Solution

▶1class Solution:
▶2    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
▶3        intersections = []
▶4        i = 0
▶5        j = 0
▶6        while i < len(firstList) and j < len(secondList):
▶7            start = max(firstList[i][0], secondList[j][0])
▶8            end = min(firstList[i][1], secondList[j][1])
▶9            if start <= end:
▶10                intersections.append([start, end])
▶11            if firstList[i][1] < secondList[j][1]:
▶12                i += 1
▶13            else:
▶14                j += 1
▶15        return intersections

05

Common pitfalls

Using union boundaries

✗ Wrong

start = min(a[0], b[0])
end = max(a[1], b[1])

✓ Right

start = max(a[0], b[0])
end = min(a[1], b[1])

Intersection keeps only points inside both intervals.

Dropping endpoint intersections

✗ Wrong

if start < end:

✓ Right

if start <= end:

Closed intervals intersect when one ends exactly where the other begins.

Advancing the later-ending interval

✗ Wrong

if a[1] < b[1]:
    j += 1

✓ Right

if a[1] < b[1]:
    i += 1

The earlier-ending interval cannot reach any later counterpart and is the one that must be discarded.

06

Edge cases

One list is empty

The loop never runs and returns an empty result.

Intervals meet at exactly one endpoint

The non-strict overlap check returns that endpoint as [x, x].

One interval fully contains another

The contained interval is returned, then its pointer advances because it ends first.

07

Complexity

Time

O(m + n)

Space

O(1) excluding output

At least one pointer advances after every comparison.