LeetCode 986: Interval List Intersections

Problem Restatement

We are given two lists of closed intervals:

firstList
secondList

Each list is sorted, and intervals inside the same list do not overlap.

We need to return all intersections between intervals from the two lists.

A closed interval [a, b] includes both endpoints. So [1, 5] and [5, 10] intersect at [5, 5].

The official constraints allow both lists to have length up to 1000, and each list is sorted with pairwise disjoint intervals.

Input and Output

Function shape:

def intervalIntersection(
    firstList: list[list[int]],
    secondList: list[list[int]],
) -> list[list[int]]:
    ...

Examples

Example 1:

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

The intersections are:

Answer:

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

Example 2:

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

There are no intervals in secondList, so there can be no intersections.

Answer:

[]

First Thought: Compare Every Pair

The direct solution is to compare every interval from firstList with every interval from secondList.

For two intervals:

[a_start, a_end]
[b_start, b_end]

their intersection starts at the later start:

start = max(a_start, b_start)

and ends at the earlier end:

end = min(a_end, b_end)

If:

start <= end

then they overlap.

class Solution:
    def intervalIntersection(
        self,
        firstList: list[list[int]],
        secondList: list[list[int]],
    ) -> list[list[int]]:
        answer = []

        for a_start, a_end in firstList:
            for b_start, b_end in secondList:
                start = max(a_start, b_start)
                end = min(a_end, b_end)

                if start <= end:
                    answer.append([start, end])

        return answer

This is correct, but it ignores the sorted structure of the input.

Problem With Comparing Every Pair

If firstList has m intervals and secondList has n intervals, comparing every pair costs:

O(m * n)

Both lists are already sorted and disjoint internally, so we can scan them more efficiently.

Key Insight

Use two pointers.

Let:

i = current interval in firstList
j = current interval in secondList

At each step, compare:

firstList[i]
secondList[j]

Their overlap, if it exists, is:

[max(start1, start2), min(end1, end2)]

After processing this pair, move the pointer whose interval ends earlier.

Why?

Suppose:

end1 < end2

Then firstList[i] ends before secondList[j].

Because secondList is sorted and disjoint, future intervals in secondList start after secondList[j] ends. So firstList[i] cannot overlap any later interval from secondList.

It is safe to move i.

Algorithm

Initialize:

i = 0
j = 0
answer = []

While both pointers are inside their lists:

1. Read the current intervals.
2. Compute the possible intersection:

   start = max(start1, start2)
   end = min(end1, end2)
3. If start <= end, append [start, end].
4. If end1 < end2, move i.
5. Otherwise, move j.

Return answer.

Correctness

At every step, the algorithm compares the earliest unprocessed interval from firstList with the earliest unprocessed interval from secondList.

For the current pair, the intersection is exactly:

[max(start1, start2), min(end1, end2)]

If the computed start is less than or equal to the computed end, the intervals share that closed interval. If not, they do not overlap.

After checking the pair, the algorithm advances the interval with the smaller end.

If firstList[i] ends before secondList[j], then firstList[i] cannot intersect any later interval in secondList, because later intervals in secondList start after the current secondList[j]. So advancing i cannot skip any valid intersection.

The same argument applies when secondList[j] ends first.

Thus every possible intersection is considered before either interval involved becomes impossible to intersect future intervals. The algorithm appends exactly the valid intersections, so the returned list is correct.

Complexity

Let m = len(firstList) and n = len(secondList).

The output itself can contain up to O(m + n) intervals.

Implementation

class Solution:
    def intervalIntersection(
        self,
        firstList: list[list[int]],
        secondList: list[list[int]],
    ) -> list[list[int]]:
        i = 0
        j = 0
        answer = []

        while i < len(firstList) and j < len(secondList):
            start1, end1 = firstList[i]
            start2, end2 = secondList[j]

            start = max(start1, start2)
            end = min(end1, end2)

            if start <= end:
                answer.append([start, end])

            if end1 < end2:
                i += 1
            else:
                j += 1

        return answer

Code Explanation

We keep one pointer for each interval list:

i = 0
j = 0

The loop continues while both lists still have intervals:

while i < len(firstList) and j < len(secondList):

Read the current intervals:

start1, end1 = firstList[i]
start2, end2 = secondList[j]

Compute their possible overlap:

start = max(start1, start2)
end = min(end1, end2)

If the overlap is non-empty, store it:

if start <= end:
    answer.append([start, end])

Then advance the interval that ends earlier:

if end1 < end2:
    i += 1
else:
    j += 1

When either list is exhausted, no more intersections are possible.

Testing

def run_tests():
    s = Solution()

    assert s.intervalIntersection(
        [[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]]

    assert s.intervalIntersection(
        [[1,3],[5,9]],
        [],
    ) == []

    assert s.intervalIntersection(
        [],
        [[4,8]],
    ) == []

    assert s.intervalIntersection(
        [[1,7]],
        [[3,5]],
    ) == [[3,5]]

    assert s.intervalIntersection(
        [[1,5]],
        [[5,10]],
    ) == [[5,5]]

    print("all tests passed")

run_tests()