986.Interval_List_Intersections(Medium).md

986. Interval List Intersections (Medium)

Date and Time: Dec 11, 2024, 9:59 (EST)

Link: https://leetcode.com/problems/interval-list-intersections

Question:

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [start_i, end_i] and secondList[j] = [start_j, end_j]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 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,3],[5,9]], secondList = []

Output: []

Constraints:

• 0 <= firstList.length, secondList.length <= 1000

• firstList.length + secondList.length >= 1

• 0 <= start_i < end_i <= 10^9

• $\text{end}i < \text{start}{i+1}$

• 0 <= start_j < end_j <= 10^9

• $\text{end}j < \text{start}{j+1}$

Walk-through:

1. Use two ptrs to keep track of the list in firstList and secondList.

2. Each time we merge the interval by [max(start_i, start_j), min(end_i, end_j)], then we update the pointers by comparing end_i, end_j, we need to keep the interval with greater end value. If end_i < end_j, we update i += 1, otherwise, we update j += 1. So the new interval can compare with the previous greater end.

Solution

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        # S: 1. Overlap, save overlap by [max(start_i, start_j), min(end_i, end_j)], then advance the smaller end
        # 2. No overlap, advance the smaller end as well
        # TC: O(m+n), SC: O(m+n)

        res = []
        l, r = 0, 0
        while l < len(firstList) and r < len(secondList):
            start_i, end_i = firstList[l]
            start_j, end_j = secondList[r]
            # No overlap
            if end_i < start_j:
                l += 1
            elif end_j < start_i:
                r += 1
            else:
                # Overlap
                res.append([max(start_i, start_j), min(end_i, end_j)])
                # Compare smaller end
                if end_i <= end_j:
                    l += 1
                else:
                    r += 1
        return res

Time Complexity: $O(n)$
Space Complexity: $O(n)$

Python Solution:

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        # Use two ptrs to access two lists
        # [max(firstList[i][0], secondList[j][0]), min(firstList[i][1], secondList[j][1])]
        # Update i or j ptr if the end of firstList[i] < secondList[j], keep the interval with greater end, we may need to compare with next interval

        # TC: O(n), n is the max length, SC: O(n)
        i, j = 0, 0
        res = []
        while i < len(firstList) and j < len(secondList):
            left = max(firstList[i][0], secondList[j][0])
            right = min(firstList[i][1], secondList[j][1])
            # Case a valid intersection exists
            if left <= right:
                res.append([left, right])
            # Update i, j ptrs base on the end
            if firstList[i][1] < secondList[j][1]:
                i += 1
            else:
                j += 1
        return res

Time Complexity: $O(n)$
Space Complexity: $O(n)$