Interval List Intersections
Problem
Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order, return the intersection of these two interval lists.
- 0 ≤ firstList.length, secondList.length ≤ 10⁴
- firstList[i].length == 2
- secondList[i].length == 2
- 0 ≤ start_i ≤ end_i ≤ 10⁹
- Intervals in each list are disjoint and sorted by start time
Example
firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]][[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]The algorithm uses two pointers to traverse both lists simultaneously. At each step, it calculates the overlap between the current intervals from both lists by taking the maximum start and minimum end. If the intervals overlap (start <= end), it adds the intersection to the result. Then, it advances the pointer of the interval that ends first, effectively discarding intervals that cannot contribute further intersections. This process continues until one list is fully traversed, ensuring all intersections are found efficiently.
Approach
Straightforward Solution
A brute-force approach would compare every interval in firstList with every interval in secondList, resulting in O(m*n) time complexity, which is inefficient for large inputs.
Core Observation
The intersection of two intervals exists if and only if the maximum of their start points is less than or equal to the minimum of their end points. Since both lists are sorted and non-overlapping internally, a two-pointer approach can efficiently find all intersections by advancing pointers based on interval end times.
Path to Optimal
PreviewThe key recognition signals are 'two sorted lists of intervals' and 'find intersections'…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse two pointers i and j starting at 0 for firstList and secondList respectively. At each step, compute the intersection between firstList[i] and secondList[j] by taking max of starts and min of ends…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(m + n)
Each pointer traverses its respective list at most once, resulting in a total of m + n steps, where m and n are the lengths of the input lists.
Space
O(m + n)
In the worst case, all intervals from both lists intersect in some way, so the output list can be as large as the sum of the input sizes. The auxiliary space used besides the output is O(1).
Pattern Spotlight
Two Pointers (Linear Merge of Sorted Intervals)
When merging or intersecting two sorted lists of intervals, advance the pointer of the interval that ends first to discard intervals that cannot contribute further intersections, ensuring a single linear pass.
Solution
| 1 | class Solution: |
| 2 | def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]: |
| 3 | i = 0 |
| 4 | j = 0 |
| 5 | |
| 6 | result = [] |
| 7 | |
| 8 | while i < len(firstList) and j < len(secondList): |
| 9 | |
| 10 | start = max(firstList[i][0], secondList[j][0]) |
| 11 | end = min(firstList[i][1], secondList[j][1]) |
| 12 | |
| 13 | if start <= end: |
| 14 | result.append([start, end]) |
| 15 | |
| 16 | if firstList[i][1] < secondList[j][1]: |
| 17 | i += 1 |
| 18 | else: |
| 19 | j += 1 |
| 20 | |
| 21 | return result |
Step-by-Step Solution
Initialize Two Pointers and Result Container
| 3 | i = 0 |
| 4 | j = 0 |
| 6 | result = [] |
Objective
To set up the initial state for simultaneous traversal of both interval lists and prepare the output list.
Key Insight
Starting pointers at zero for both lists leverages their sorted order. An empty result list is necessary to accumulate intersections as they are found. This setup is the foundation for the linear-time two-pointer traversal.
Interview Quick-Check
Core Logic
Initializing pointers at the start of each list enables a linear scan that exploits the sorted, disjoint nature of the intervals.
State & Boundaries
The result list must be initialized empty to collect all intersections found during traversal.
Traverse Both Lists to Find Interval Intersections
To iterate through both lists simultaneously, identify overlapping intervals, and record their intersections.
Return the Complete List of Intersections
To output the accumulated list of intersecting intervals after traversal completes.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if start <= end:Check if the intervals overlap (start <= end).
This conditional is the critical correctness check that determines whether the current intervals intersect, enabling the algorithm to append only valid intersections.
if firstList[i][1] < secondList[j][1]:Compare the end points of the current intervals to decide which pointer to advance.
This comparison embodies the core two-pointer strategy, ensuring progress and preventing missed intersections by moving past the interval that cannot overlap with future intervals.
Full line-by-line criticality + rationale for all 13 lines available on Pro.
Test Your Understanding
Why does advancing the pointer of the interval with the smaller end guarantee that no intersections are missed?
See the answer with Pro.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Interval List Intersections from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Interval List Intersections drill