How-to Intermediate

Chapter 1 Updated April 21, 2026

Interval List Intersections

Two pointers; advance the one whose interval ends first.

Full 5m
Revision 2m
Flow 1m

LeetCode #986 — one-liner.

Given two sorted, disjoint interval lists, return the list of all their pairwise intersections.

Two pointers, advance the earlier end.

Both lists are already sorted and disjoint — no need to re-sort.
At each step compute the candidate intersection [max(starts), min(ends)]; if lo ≤ hi, it’s a real intersection.
Advance the pointer whose interval ends first — the other list can still yield more intersections with the current interval.

One while-loop.

i = j = 0
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

Linear in total size.

Time O(m + n) — each pointer advances at most m or n times.
Space O(m + n) — worst-case output size.

Three to remember.

Either list empty → return [].
Point intersection [5, 5] — valid because lo = hi = 5 and 5 ≤ 5.
No overlap anywhere → lo > hi every step → result stays empty.

Comments

Comments are disabled in this environment. Set PUBLIC_GISCUS_REPO, PUBLIC_GISCUS_REPO_ID, and PUBLIC_GISCUS_CATEGORY_ID to enable.