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
The key recognition signals are 'two sorted lists of intervals' and 'find intersections'. These indicate the Two Pointers pattern because the sorted order allows linear traversal with pointers, and the disjoint property ensures no overlapping intervals within a list, simplifying intersection checks. By comparing intervals at pointers and advancing the pointer with the smaller end, the algorithm discards intervals that cannot intersect further, achieving O(m + n) time.
Optimal Approach
Use 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. If they intersect, add to result. Then advance the pointer of the interval that ends first to move forward. Continue until one list is exhausted. This guarantees all intersections are found in linear time.
Time
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
| 8 | while i < len(firstList) and j < len(secondList): |
| 10 | start = max(firstList[i][0], secondList[j][0]) |
| 11 | end = min(firstList[i][1], secondList[j][1]) |
| 13 | if start <= end: |
| 14 | result.append([start, end]) |
| 16 | if firstList[i][1] < secondList[j][1]: |
| 17 | i += 1 |
| 18 | else: |
| 19 | j += 1 |
Objective
To iterate through both lists simultaneously, identify overlapping intervals, and record their intersections.
Key Insight
At each iteration, the intersection is determined by the maximum start and minimum end of the current intervals. If these values define a valid interval (start <= end), it is appended to the result. Advancing the pointer of the interval that ends first ensures progress and avoids missing any intersections, as intervals are sorted and non-overlapping within each list.
Interview Quick-Check
Core Logic
The algorithm calculates the intersection by taking the max of start points and min of end points, then advances the pointer of the interval with the smaller end to efficiently find all intersections.
State & Boundaries
The loop continues while both pointers are within their respective list bounds, ensuring all intervals are considered.
Common Pitfalls & Bugs
Failing to advance the pointer of the interval with the smaller end can cause infinite loops or missed intersections.
Complexity
This approach guarantees O(m + n) time complexity by processing each interval at most once.
Return the Complete List of Intersections
| 21 | return result |
Objective
To output the accumulated list of intersecting intervals after traversal completes.
Key Insight
Once one list is fully traversed, no further intersections are possible. Returning the result list provides the final answer as required by the problem.
Interview Quick-Check
Core Logic
Returning the result after traversal ensures all intersections found are delivered as the solution.
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.
start = max(firstList[i][0], secondList[j][0])Calculate the start of the intersection as the maximum of the two intervals' start points.
The intersection cannot start before both intervals have started, so the maximum start point defines the earliest possible overlap.
end = min(firstList[i][1], secondList[j][1])Calculate the end of the intersection as the minimum of the two intervals' end points.
The intersection cannot extend beyond the earliest finishing interval, so the minimum end point defines the latest possible overlap.
i = 0Initialize pointer i for firstList at 0.
Starting at the beginning of firstList allows linear traversal leveraging the sorted order of intervals.
j = 0Initialize pointer j for secondList at 0.
Starting at the beginning of secondList enables synchronized traversal with firstList.
result.append([start, end])Append the intersection interval to the result list.
Recording the valid intersection ensures the output contains all overlapping intervals between the two lists.
i += 1Advance pointer i if firstList's interval ends before secondList's.
Moving pointer i discards the current interval in firstList that cannot intersect with any future intervals in secondList beyond pointer j.
else:Handle the case where the interval in secondList finishes earlier or at the same time.
If firstList[i][1] is not less than secondList[j][1], the interval in secondList ends first (or both end simultaneously). Advancing j discards the interval that cannot intersect with any future intervals in firstList.
j += 1Advance pointer j to the next interval in secondList.
Since the current interval in secondList has finished, it cannot intersect with any later intervals from firstList. Moving j ensures the algorithm progresses while preserving correctness.
while i < len(firstList) and j < len(secondList):Loop while both pointers are within their respective lists.
Ensures that the algorithm processes intervals only while both lists have remaining intervals to compare, preventing out-of-bounds errors.
result = []Create an empty list to store interval intersections.
This list accumulates all valid intersections found during traversal, forming the final output.
return resultReturn the list of all found interval intersections.
This provides the final answer as required by the problem, containing all overlapping intervals between the two input lists.
Test Your Understanding
Why does advancing the pointer of the interval with the smaller end guarantee that no intersections are missed?
Because intervals are sorted and disjoint within each list, the interval with the smaller end cannot intersect with any future intervals in the other list beyond the current pointer, so advancing its pointer discards it safely without missing any intersections.
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