How do you approach Interval List Intersections?

Two intervals intersect on [max(starts), min(ends)] - and that is a real interval only when max(starts) <= min(ends).

What is the time complexity of Interval List Intersections?

Time complexity: O(m + n). Space complexity: O(1) beyond the output..

What are common mistakes on Interval List Intersections?

Not sorting first. Nearly every interval algorithm assumes the list is ordered by start, and skipping that step gives answers that are right on the sample and wrong everywhere else. Treating touching intervals as overlapping (or not) without checking which the problem means. Mutating the input intervals while iterating over them.

Sitelet https://gitgood.dev/coding/interval-list-intersections

gitGood.dev

← Back to problems

Interval List Intersections

MediumAlgorithms

Description

You are given two lists of closed intervals, firstList and secondList. Each list is sorted by start time and is internally non-overlapping.

Return the intersection of the two lists: every interval covered by both.

A closed interval [a,b] includes both endpoints, so [1,3] and [3,5] intersect in the single point [3,3].

Example 1

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]

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

Example 2

Input: firstList = [[1,7]], secondList = [[3,10]]

Output: [[3,7]]

Example 3

Input: firstList = [[1,3],[5,9]], secondList = []

Output: []

Constraints

- 0 <= firstList.length, secondList.length <= 1000 - Each list is sorted and internally disjoint - 0 <= start <= end <= 10^9 - Solve in O(m + n) with two pointers.

Interval List Intersections: approach, complexity and pitfalls

A medium intervals problem, graded against 6 test cases (3 of them hidden).

The pattern: Intervals

Sorting by start or end, then merging or scheduling overlapping ranges.

Reach for it when you see: Meetings, bookings, ranges, or anything with a start and an end.

If you are stuck

Show the 3-step hint ladder

Two intervals intersect on [max(starts), min(ends)] - and that is a real interval only when max(starts) <= min(ends).
Walk both lists with one pointer each. Test the current pair, then advance the pointer whose interval ends FIRST.
Advancing the earlier-ending interval is safe: it cannot intersect anything later in the other list, since that list is sorted.

The optimal approach

Show the approach: Two pointers, advance the one that ends first

For any pair of intervals, the overlap is `[max(startA, startB), min(endA, endB)]`, and it exists only if that low bound does not exceed that high bound. Because these are closed intervals the test is `<=`, not `<` - which is why `[1,3]` and `[3,5]` produce the degenerate but valid `[3,3]`.

The pairing strategy is what makes it linear. Keep one pointer per list, test the current pair, and then advance the pointer whose interval has the smaller end. That interval is finished: everything remaining in the other list starts at or after the current position and ends later, so it cannot intersect anything else. Advancing the other pointer instead would skip real intersections.

Each step consumes one interval, so the walk is O(m + n) - no sorting, since both inputs arrive sorted.

Time: O(m + n)
Space: O(1) beyond the output.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Intervals mistakes

These apply to the pattern as a whole, not just this problem.

Not sorting first. Nearly every interval algorithm assumes the list is ordered by start, and skipping that step gives answers that are right on the sample and wrong everywhere else.
Treating touching intervals as overlapping (or not) without checking which the problem means.
Mutating the input intervals while iterating over them.