Interval List Intersections Python Solution

LeetCode 986, Medium. Topics: Array, Two Pointers, Sweep Line. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 13 parametrized pytest cases, and a playground notebook:

lcpy gen -n 986   # by problem number
lcpy gen -s interval_list_intersections   # by problem name

Problem

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. 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].

Examples

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]]

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

Constraints

0 <= firstList.length, secondList.length <= 1000
firstList.length + secondList.length >= 1
0 <= starti < endi <= 10^9
endi < starti+1
0 <= startj < endj <= 10^9
endj < startj+1

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(m + n)
    # Space: O(1) excluding output
    def interval_intersection(
        self, first_list: list[list[int]], second_list: list[list[int]]
    ) -> list[list[int]]:
        result: list[list[int]] = []
        i = j = 0
        while i < len(first_list) and j < len(second_list):
            lo = max(first_list[i][0], second_list[j][0])
            hi = min(first_list[i][1], second_list[j][1])
            if lo <= hi:
                result.append([lo, hi])
            if first_list[i][1] < second_list[j][1]:
                i += 1
            else:
                j += 1
        return result

Complexity

Time	Space
O(m + n)	O(1) excluding output

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Interval List Intersections Python Solution

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags