Interval List Intersections (LeetCode 986)

The problem

You get two lists of closed intervals, A and B. Each list is sorted and its intervals do not overlap each other. Return every interval where the two lists overlap.

A = [[0, 2], [5, 10], [13, 23], [24, 25]]
B = [[1, 5], [8, 12], [15, 24], [25, 26]]

Output: [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]

For example [0, 2] and [1, 5] share [1, 2], and [5, 10] and [1, 5] share just the point [5, 5].

How to think about it

Start with brute force. Compare every interval in A with every interval in B and keep the non-empty overlaps. That is O(m·n), and it ignores that both lists are sorted.

How to intersect two intervals. The overlap of [a1, a2] and [b1, b2] starts at the later start and ends at the earlier end: [max(a1, b1), min(a2, b2)]. It is real only if lo <= hi.

The key insight: advance the one that ends first. Look at the current pair A[i], B[j]. Whichever ends earlier cannot overlap anything further in the other list, because every later interval there starts even later. So it is finished; move its pointer. The other interval might still overlap the next one, so keep it. Each step moves one pointer, so the walk is linear.

Which pattern is this? Intervals with two pointers, like merging two sorted lists. The tell is “two sorted interval lists”.

Approach

1. Set i = j = 0 and res = [].
2. While both pointers are in range, compute lo = max(A[i][0], B[j][0]) and hi = min(A[i][1], B[j][1]).
3. If lo <= hi, append [lo, hi].
4. If A[i] ends before B[j], advance i; otherwise advance j.
5. Return res.

Solution

def interval_intersection(A, B):
    i = j = 0; res = []
    while i < len(A) and j < len(B):
        lo = max(A[i][0], B[j][0]); hi = min(A[i][1], B[j][1])   # candidate overlap
        if lo <= hi: res.append([lo, hi])                       # non-empty: keep it
        if A[i][1] < B[j][1]: i += 1                            # A[i] ends first: done with it
        else: j += 1
    return res
# interval_intersection([[0,2],[5,10],[13,23],[24,25]], [[1,5],[8,12],[15,24],[25,26]])
#   -> [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Dry run

i runs off the end of A, so the loop stops with six intersections.

Complexity

• Time: O(m + n). Every iteration advances one pointer.
• Space: O(1) extra. Only the output list grows (it has at most m + n entries).

Edge cases and pitfalls

• Either list empty returns [].
• Single-point overlaps like [5, 5] count because intervals are closed; use lo <= hi, not lo < hi.
• Equal ends: when A[i][1] == B[j][1] the code advances j. Either choice is fine, since both are finished and the other will be advanced next round.
• Advancing by start instead of end skips overlaps: an interval that starts early but ends late can still overlap the next interval in the other list.

Related problems

• Merge Intervals (LeetCode 56): union of intervals instead of intersection.
• Merge Two Sorted Lists (LeetCode 21): the same “advance the smaller one” two-pointer walk.
• Employee Free Time (LeetCode 759): working across several people’s interval lists at once.