MediumArrayTwo PointersIntervals

Interval List Intersections

1 approach, code in every language

You are handed two lists of closed intervals, each list individually sorted by start value and internally free of overlaps. Compute the intersection of the two lists: every span that lies inside an interval from the first list and simultaneously inside an interval from the second list.

Return these overlapping spans as a sorted list of closed intervals. A shared single point counts as a valid intersection.

Example 1

Input: firstList = [[0,2],[5,10]], secondList = [[1,5],[8,12]]

Output: [[1,2],[5,5],[8,10]]

0-2 meets 1-5 at 1-2, 5-10 meets 1-5 at the single point 5, and 5-10 meets 8-12 at 8-10.

Example 2

Input: firstList = [[1,4]], secondList = [[5,7]]

Output: []

The only interval in each list sits entirely apart from the other, so there is no overlap.

Constraints

0 ≤ firstList.length, secondList.length ≤ 1000
firstList.length + secondList.length ≥ 1
0 ≤ start ≤ end ≤ 10^9
Each list is sorted by start and contains no overlapping intervals

Two pointers across both lists

Advance one pointer per list, compute the overlap of the current pair, record it when valid, then move past whichever interval ends first.

Loading animation…

Intuition

Because both lists are already sorted by start, we can compare one interval from each at a time. The overlap of two intervals is the range from the larger of the two starts to the smaller of the two ends; if that low bound does not exceed the high bound, we found a genuine intersection. After checking a pair, the interval that finishes earlier can never intersect anything further ahead, so we discard it by moving its pointer forward. This keeps a single forward sweep over both lists.

Algorithm walkthrough

1Set a pointer i for the first list and j for the second, both starting at zero.
2While both pointers are in range, take lo as the max of the two starts and hi as the min of the two ends.
3If lo is less than or equal to hi, push [lo, hi] onto the result since it is a real overlap.
4Move forward the pointer whose current interval has the smaller end value.
5Stop when either list is exhausted and return the collected intersections.

Implementation

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        result = []
        i, j = 0, 0
        while i < len(firstList) and j < len(secondList):
            lo = max(firstList[i][0], secondList[j][0])
            hi = min(firstList[i][1], secondList[j][1])
            if lo <= hi:
                result.append([lo, hi])
            if firstList[i][1] < secondList[j][1]:
                i += 1
            else:
                j += 1
        return result

Time

O(m + n)

Space

O(m + n)

Each pointer advances at most through its own list, so the sweep is linear in the combined length. Space is bounded by the number of intersections stored in the output.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Shared Observation Windows is our own problem on the technique behind Interval List Intersections: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free