Interval List Intersections

Medium#986two lists

You get two lists of intervals. Each is sorted, and inside one list no two intervals overlap. Return every common part of an interval from the first list and an interval from the second, in order. A common part can be a single point. Our example: A = [1, 3], [5, 9], [11, 12], B = [0, 2], [4, 6], [8, 12] — the answer is [1, 2], [5, 6], [8, 9], [11, 12].

986 Interval List IntersectionsWalkthrough · 1×

Example: A = [1, 3], [5, 9], [11, 12], B = [0, 2], [4, 6], [8, 12]. Each list is one row on the axis; the lines show lo and hi, the result is at the bottom.

ABresult0123456789101112
not looked at yetA[i] and B[j], the new common partalready handledresult

No common parts yet

01/38
restart · back · play · step
Speed
1function intervalIntersection(A, B):
2 result = []
3 i = 0; j = 0
4 while i < len(A) and j < len(B):
5 lo = max(A[i].start, B[j].start)
6 hi = min(A[i].end, B[j].end)
7 if lo <= hi:
8 add [lo, hi] to result
9 if A[i].end < B[j].end:
10 i = i + 1
11 else:
12 j = j + 1
13 return result
state
result
[]
i
–
j
–
lo
–
hi
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Two intervals share the part from the later start, lo, to the earlier end, hi. If lo > hi, one ends before the other starts and they share nothing.
  2. The interval that ends first is done: every later interval of the other list starts after the current one ends, and that is already past this end. So it moves on, and the other one stays.
  3. The one that stays can meet more: B’s [8, 12] shares [8, 9] with [5, 9] and then [11, 12] with [11, 12]. Moving both at once would lose the second piece.

Complexity

Time O(n + m): each step moves one of the two lists forward. Memory O(1) besides the result.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.