Domain 2MediumMEDIUM

Interval List Intersections

Given two sorted lists of disjoint intervals, find their intersection using a linear time two-pointer approach. This solution iterates through both arrays simultaneously to identify overlapping ranges efficiently.

Domain: medium•Updated: 2026-09-05
#Two Pointers#List/Array#O(N+M)#O(1)

Problem Breakdown

We need to compute the list of intersections between firstList and secondList.

  • Inputs: Two lists (firstList, secondList) where each element is a [start, end] pair. Both are sorted by start time and intervals within each list do not overlap (disjoint).
  • Output: A new list of closed interval pairs representing the intersection points between the two input lists. If no intersections exist, return an empty list.
  • Constraints & Edge Cases:
    • Inputs can be empty ([]), but at least one must contain intervals based on constraints (though logic handles both empty).
    • Coordinates are up to 10910^9, requiring pointer arithmetic rather than array mapping.
    • Intersections can be single points where start == end.

Intuition

Since the input lists are sorted by start time and disjoint within themselves, we do not need nested loops (which would yield O(N*M)). Instead, a Two Pointers approach allows us to traverse both lists in linear time.

  • We maintain pointers for each list (i and j).
  • At any step, the interval that ends earlier cannot intersect with any future intervals from the other list because all subsequent intervals start after its end (due to sorting).
  • Therefore, we always advance the pointer corresponding to the interval that finishes first. This ensures every element is visited at most once.

Approach

  1. Initialize pointers i = 0 and j = 0.
  2. Loop while both pointers are within bounds of their respective lists.
  3. Identify current intervals: intervalA from firstList[i] and intervalB from secondList[j].
  4. Compute the intersection range boundaries:
    • Start is max(intervalA.start, intervalB.start).
    • End is min(intervalA.end, intervalB.end).
  5. If valid overlap exists (start <= end), add [start, end] to results.
  6. Advance the pointer of whichever list’s current interval ends earlier (or equal). This discards intervals that have finished their potential intersection window relative to the other sorted stream.

Complexity Analysis

  • Time Complexity: O(N+M)O(N + M) where N and M are lengths of firstList and secondList. Each element is processed exactly once by its respective pointer; no backtracking occurs.
  • Space Complexity: O(1)O(1) auxiliary space (excluding the output list which requires O(K)O(K) for K intersections).

Solution

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        i = 0
        j = 0
        result = []
        
        while i < len(firstList) and j < len(secondList):
            start1, end1 = firstList[i]
            start2, end2 = secondList[j]
            
            # Determine the intersection range boundaries
            overlap_start = max(start1, start2)
            overlap_end = min(end1, end2)
            
            # If valid intersection exists (start <= end), add to result. 
            # This handles single-point overlaps correctly as well.
            if overlap_start <= overlap_end:
                result.append([overlap_start, overlap_end])
            
            # Advance the pointer of the interval that ends first or equal.
            # Once an interval finishes, it cannot intersect with subsequent intervals in the other list 
            # because they are sorted and disjoint within their own lists.
            if end1 < end2:
                i += 1
            else:
                j += 1
                
        return result

Edge Cases Handled

  • Empty Lists: If either firstList or secondList is empty, the loop condition fails immediately and an empty list is returned.
  • No Intersection: Disjoint intervals (e.g., [0,2] vs [5,10]) result in advancing pointers until one list is exhausted without adding results.
  • Single Point Overlap: The logic overlap_start <= overlap_end correctly captures cases where start equals end (e.g., intersection at a single point).
  • One List Fully Contained: If an interval from one list is completely inside the other, the pointer for the inner interval advances first until it matches or exceeds bounds.