#986

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Interval List Intersections

This problem requires finding the intersection of two lists of intervals using a two-pointer technique with invariant tracking.

array two pointers line sweep

Problem Statement

You are given two sorted lists of closed intervals, firstList and secondList, where each list contains disjoint intervals. Each interval is represented as a pair of integers [start, end]. The goal is to return the intersection of these two lists, which consists of the intervals that are common to both lists.

A closed interval [a, b] represents the set of real numbers from a to b, inclusive. The input lists are sorted by their starting values. If there is no overlap between the intervals, you should return an empty list. The challenge is to find the intersection of these intervals efficiently, using a two-pointer technique to scan through both lists.

Examples

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 details omitted.

Example 2

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

Output: []

Example details omitted.

Constraints

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

Solution Approach

Two-pointer scanning

The key to solving this problem efficiently is the two-pointer technique. We maintain two pointers, one for each list. Starting from the beginning of both lists, we compare the current intervals from both lists to see if they overlap. If they do, we record the intersection, then move the pointer that points to the interval with the earlier ending time.

Invariant tracking

As we scan through the intervals, we need to maintain certain invariants to ensure correctness. The main invariant is that we always track the current range of intersection. If the current interval from one list does not intersect with the interval from the other list, we move the pointer of the list with the smaller interval to attempt finding a new intersection.

Efficient traversal

By using the two-pointer technique, we can ensure that each list is traversed only once, leading to an O(n + m) time complexity, where n and m are the lengths of the two input lists. This makes the approach highly efficient even for the maximum input size.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach is O(n + m) because we traverse both lists once, where n and m are the lengths of firstList and secondList, respectively. The space complexity is O(k), where k is the number of intersecting intervals, since we store the result of the intersections in a new list.

What Interviewers Usually Probe

The candidate understands how to implement a two-pointer technique efficiently.
They should be able to explain the trade-off of traversing both lists in a single pass rather than checking each pair of intervals individually.
The candidate can identify the necessary conditions for intervals to overlap and the corresponding actions to move the pointers accordingly.

Common Pitfalls or Variants

Common pitfalls

Incorrectly handling cases where intervals do not overlap, resulting in missing intersections.
Failing to move the correct pointer after finding an intersection, leading to unnecessary comparisons.
Not keeping track of the current intersecting range properly, which could lead to incorrect results.

Follow-up variants

The problem can be extended to find the union of two interval lists instead of the intersection.
A variant could involve unsorted interval lists, requiring sorting before applying the two-pointer technique.
The problem could also ask to handle intervals with more complex ranges, such as half-open intervals.

FAQ

What is the most efficient approach for solving the Interval List Intersections problem?

The most efficient approach is to use the two-pointer technique, where you traverse both lists simultaneously, tracking the current intersection and adjusting the pointers accordingly.

How does the two-pointer technique work for Interval List Intersections?

The two-pointer technique involves using two pointers, one for each list, and comparing the current intervals. If they overlap, we record the intersection and move the pointer of the interval with the smaller ending value.

What is the time complexity of the solution to the Interval List Intersections problem?

The time complexity of the solution is O(n + m), where n and m are the lengths of the two input lists, since both lists are traversed exactly once.

How do you handle cases where the intervals do not overlap in the Interval List Intersections problem?

If the intervals do not overlap, we move the pointer of the list with the smaller ending value to attempt finding a new intersection in the subsequent comparisons.

Can the Interval List Intersections problem be solved with a different algorithm?

While the two-pointer technique is the most efficient solution, you could solve it with a brute-force approach by checking all pairs of intervals, but this would lead to higher time complexity.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def intervalIntersection(
        self, firstList: List[List[int]], secondList: List[List[int]]
    ) -> List[List[int]]:
        i = j = 0
        ans = []
        while i < len(firstList) and j < len(secondList):
            s1, e1, s2, e2 = *firstList[i], *secondList[j]
            l, r = max(s1, s2), min(e1, e2)
            if l <= r:
                ans.append([l, r])
            if e1 < e2:
                i += 1
            else:
                j += 1
        return ans

Continue Practicing

#977 squares of a sorted array #969 pancake sorting #962 maximum width ramp