Problem Description

You are given two lists of closed intervals: firstList and secondList. Each interval is represented as [start, end] where start is the beginning of the interval and end is the ending of the interval.

Key properties of the input:

• Each list contains intervals that are pairwise disjoint (no two intervals in the same list overlap)
• Each list is sorted in order
• A closed interval [a, b] includes all values x where a ≤ x ≤ b

Your task is to find all the intersections between intervals from firstList and intervals from secondList.

An intersection between two intervals occurs when they share common values. For example:

• The intersection of [1, 3] and [2, 4] is [2, 3] (the overlapping portion)
• If two intervals don't overlap, they have no intersection

You need to return a list containing all the intersection intervals.

Example visualization: If firstList = [[0,2], [5,10], [13,23], [24,25]] and secondList = [[1,5], [8,12], [15,24], [25,26]], the intersections would be:

• [0,2] and [1,5] → intersection is [1,2]
• [5,10] and [1,5] → intersection is [5,5]
• [5,10] and [8,12] → intersection is [8,10]
• [13,23] and [15,24] → intersection is [15,23]
• [24,25] and [15,24] → intersection is [24,24]
• [24,25] and [25,26] → intersection is [25,25]

The output would be: [[1,2], [5,5], [8,10], [15,23], [24,24], [25,25]]

Intuition

Since both lists are sorted and contain non-overlapping intervals within each list, we can use a two-pointer approach to efficiently find all intersections.

The key insight is that we don't need to check every interval in firstList against every interval in secondList. Instead, we can traverse both lists simultaneously using two pointers, i and j.

For any two intervals to intersect, they must overlap. The intersection of two intervals [s1, e1] and [s2, e2] can be calculated as:

• The start of the intersection is the maximum of the two start points: max(s1, s2)
• The end of the intersection is the minimum of the two end points: min(e1, e2)
• If max(s1, s2) <= min(e1, e2), then the intervals intersect

The crucial decision is which pointer to advance after processing a pair of intervals. We should advance the pointer pointing to the interval that ends earlier because:

• If interval A ends before interval B, then A cannot possibly intersect with any intervals that come after B in the other list
• However, B might still intersect with the next interval after A

For example, if we have firstList[i] = [1, 3] and secondList[j] = [2, 5]:

• Their intersection is [2, 3]
• Since firstList[i] ends at 3 (earlier than 5), we advance i
• We keep j the same because [2, 5] might still intersect with the next interval in firstList

This greedy approach ensures we find all intersections while only visiting each interval once, giving us an optimal O(m + n) time complexity where m and n are the lengths of the two lists.

Learn more about Two Pointers and Line Sweep patterns.

Solution Approach

The implementation uses a two-pointer technique to traverse both interval lists simultaneously:

Initialization:

• Set two pointers i = 0 and j = 0 to track positions in firstList and secondList respectively
• Create an empty list ans to store the intersection results

Main Loop: The algorithm continues while both pointers are within bounds: while i < len(firstList) and j < len(secondList)

For each iteration:

1. Extract interval boundaries:

   s1, e1, s2, e2 = *firstList[i], *secondList[j]

   This unpacks the current intervals into their start and end points using Python's unpacking operator.

2. Calculate potential intersection:

   l, r = max(s1, s2), min(e1, e2)

   • l (left boundary) = maximum of the two start points
   • r (right boundary) = minimum of the two end points

3. Check if intersection exists:

   if l <= r:
       ans.append([l, r])

   If the left boundary is less than or equal to the right boundary, we have a valid intersection interval [l, r].

4. Advance the appropriate pointer:

   if e1 < e2:
       i += 1
   else:
       j += 1

   • If firstList[i] ends before secondList[j], advance pointer i
   • Otherwise, advance pointer j
   • This ensures we don't miss any potential intersections with the interval that extends further

Example walkthrough: For firstList = [[0,2], [5,10]] and secondList = [[1,5], [8,12]]:

• Step 1: Compare [0,2] and [1,5] → intersection [1,2], advance i (since 2 < 5)
• Step 2: Compare [5,10] and [1,5] → intersection [5,5], advance j (since 5 < 10)
• Step 3: Compare [5,10] and [8,12] → intersection [8,10], advance i (since 10 < 12)
• Step 4: i is out of bounds, loop ends

The algorithm efficiently finds all intersections in O(m + n) time with O(1) extra space (excluding the output array).

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input:

• firstList = [[1,4], [6,8]]
• secondList = [[2,5], [7,10]]

Goal: Find all intersections between intervals from both lists.

Initialization:

• i = 0, j = 0 (pointers for firstList and secondList)
• ans = [] (result array)

Step 1: Compare firstList[0] = [1,4] with secondList[0] = [2,5]

• Extract boundaries: s1=1, e1=4, s2=2, e2=5
• Calculate intersection: l = max(1,2) = 2, r = min(4,5) = 4
• Since l ≤ r (2 ≤ 4), we have intersection [2,4]
• Add [2,4] to result: ans = [[2,4]]
• Compare endpoints: e1=4 < e2=5, so advance i to 1
• Current state: i=1, j=0

Step 2: Compare firstList[1] = [6,8] with secondList[0] = [2,5]

• Extract boundaries: s1=6, e1=8, s2=2, e2=5
• Calculate intersection: l = max(6,2) = 6, r = min(8,5) = 5
• Since l > r (6 > 5), no intersection exists
• Compare endpoints: e1=8 > e2=5, so advance j to 1
• Current state: i=1, j=1

Step 3: Compare firstList[1] = [6,8] with secondList[1] = [7,10]

• Extract boundaries: s1=6, e1=8, s2=7, e2=10
• Calculate intersection: l = max(6,7) = 7, r = min(8,10) = 8
• Since l ≤ r (7 ≤ 8), we have intersection [7,8]
• Add [7,8] to result: ans = [[2,4], [7,8]]
• Compare endpoints: e1=8 < e2=10, so advance i to 2
• Current state: i=2, j=1

Step 4: i=2 is out of bounds (firstList has only 2 elements)

• Loop terminates

Final Result: [[2,4], [7,8]]

The algorithm efficiently found both intersections by advancing the pointer of the interval that ended earlier, ensuring no potential intersections were missed while visiting each interval exactly once.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n) where m is the length of firstList and n is the length of secondList.

The algorithm uses a two-pointer approach, traversing through both lists simultaneously. In each iteration, we either increment pointer i or pointer j (never both), moving through the intervals linearly. Since each interval is visited at most once, and we process at most m + n intervals total, the time complexity is linear in the sum of the input sizes.

Space Complexity: O(1) for auxiliary space, or O(k) for total space where k is the number of intersections.

The algorithm uses only a constant amount of extra space for variables i, j, s1, e1, s2, e2, l, and r. However, if we consider the output array ans as part of the space complexity, it would be O(k) where k is the number of intersecting intervals. In the worst case, k could be min(m, n) when all intervals from the shorter list intersect with intervals from the longer list.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Pointer Advancement Logic

The Pitfall: A common mistake is advancing both pointers when an intersection is found, or using incorrect logic to decide which pointer to advance:

# WRONG: Advancing both pointers after finding intersection
if intersection_start <= intersection_end:
    result.append([intersection_start, intersection_end])
    i += 1
    j += 1  # This will miss potential intersections!

Why it's wrong: An interval from one list can intersect with multiple intervals from the other list. By advancing both pointers, you'll miss these additional intersections.

Example where this fails:

• firstList = [[1,10]], secondList = [[2,3], [4,5], [6,7]]
• The interval [1,10] should intersect with all three intervals in secondList
• If you advance both pointers after finding [2,3], you'll miss [4,5] and [6,7]

The Solution: Always advance the pointer of the interval that ends first:

if end1 < end2:
    i += 1
else:
    j += 1

2. Edge Case: Single-Point Intersections

The Pitfall: Using strict inequality (<) instead of <= when checking for valid intersections:

# WRONG: This misses single-point intersections
if intersection_start < intersection_end:  # Should be <=
    result.append([intersection_start, intersection_end])

Example where this fails:

• firstList = [[1,3]], secondList = [[3,5]]
• The intersection should be [3,3] (a single point)
• With <, this valid intersection would be missed

The Solution: Always use <= to include single-point intersections:

if intersection_start <= intersection_end:
    result.append([intersection_start, intersection_end])

3. Forgetting to Handle Empty Lists

The Pitfall: Not considering that one or both input lists might be empty. While the two-pointer approach naturally handles this (the while loop condition fails immediately), some might try to optimize or add unnecessary checks that break this natural handling.

The Solution: The standard two-pointer approach with while i < len(firstList) and j < len(secondList) naturally handles empty lists without additional checks.