Coding Puzzle: List Interval Intersections

• Leetcode 986
• Difficulty: Medium

Problem Definition

Given 2 lists of sorted non-overlapping intervals in the format [start, end] with both the start and end being included in the interval, return the intersections for the 2 lists.

Example

A test case to verify our solution.

assert interval_intersections([[1,2],[3,4],[5,6],[7,8]], [[1,4],[6,8]]) == [[1,4],[6,6],[7,8]]

Solution

def intersections(arr1: list[list[int]], arr2: list[list[int]]) -> list[list[int]]:
    res = []
    i1, i2 = 0, 0
    while i1 < len(arr1) and i2 < len(arr2):
        start1, end1 = arr1[i1]
        start2, end2 = arr2[i2]
        if (start1 >= start2 and start1 <= end2) or (start2 >= start1 and start2 <= end1):
            start = max(start1, start2)
            end = min(end1, end2)
            res.append([start, end])
        if end1 <= end2:
            i1 += 1
        else:
            i2 += 1
    return res

Complexity

Let $n_1 =$ len(arr1), $n_2 =$ len(arr2).

Runtime complexity should be $O(n_1 + n_2)$.

Auxiliary space complexity should be $O(n_1 + n_2)$.