LeetCode 986 - Interval List Intersections
The problem gives us two lists of closed intervals. Each interval is represented as [start, end], meaning every value from start through end, inclusive, belongs to that interval.
Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Sweep Line
Solution
Problem Understanding
The problem gives us two lists of closed intervals. Each interval is represented as [start, end], meaning every value from start through end, inclusive, belongs to that interval.
The important guarantees are:
- Each individual list is already sorted by interval start time
- Intervals inside the same list do not overlap each other
- The intervals are closed intervals, meaning endpoints count as part of the interval
We need to compute all intersections between intervals from firstList and intervals from secondList.
An intersection between two intervals exists when they overlap. For example:
[1, 5]and[2, 7]intersect at[2, 5][3, 4]and[5, 6]do not intersect[5, 10]and[10, 12]intersect at[10, 10]because intervals are closed
The output should contain every overlapping interval between the two lists, in sorted order.
The constraints are relatively small, with at most 1000 intervals across both lists. Even though this size would allow a quadratic solution to pass in practice, the structure of the input strongly suggests a more efficient linear solution. Since both lists are already sorted and internally non-overlapping, we can process them similarly to the merge phase of merge sort.
Several edge cases are important:
- One or both lists may be empty
- Intervals may touch at exactly one endpoint
- One interval may completely contain another
- Multiple intervals in one list may overlap different intervals in the other list
- The lists are guaranteed sorted and non-overlapping internally, so we never need to merge intervals within the same list
Approaches
Brute Force Approach
The most direct solution is to compare every interval in firstList against every interval in secondList.
For each pair of intervals:
- Compute the overlap start as
max(start1, start2) - Compute the overlap end as
min(end1, end2) - If
overlap_start <= overlap_end, then the intervals intersect
This approach is correct because every possible pair is checked, so no valid intersection can be missed.
However, the time complexity is inefficient. If there are n intervals in firstList and m intervals in secondList, we perform n * m comparisons.
The input structure gives us something much better to exploit. Since both lists are sorted and internally disjoint, once we know which interval ends first, we also know which interval can never overlap future intervals.
Optimal Two Pointer Approach
The key observation is that intervals are sorted and non-overlapping within each list.
Suppose we are currently comparing:
firstList[i]secondList[j]
After checking their intersection, whichever interval ends first can safely be discarded.
Why?
Because intervals are sorted. If firstList[i] ends before secondList[j], then firstList[i] cannot possibly overlap with any future interval in secondList, since future intervals start even later.
This allows us to move through both lists in a single pass using two pointers.
This transforms the problem into a linear-time merge-style traversal.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n × m) | O(1) excluding output | Compare every interval pair |
| Optimal | O(n + m) | O(1) excluding output | Two pointers exploit sorted order |
Algorithm Walkthrough
- Initialize two pointers,
iandj, both starting at0.
Pointer i tracks the current interval in firstList, while pointer j tracks the current interval in secondList.
2. Create an empty result list.
This list will store all intersections we discover during traversal. 3. Continue processing while both pointers remain within bounds.
We stop as soon as one list is exhausted because no more intersections are possible afterward. 4. Extract the current intervals.
Let:
first = firstList[i]second = secondList[j]
- Compute the possible overlap.
The overlap begins at:
max(first.start, second.start)
because the intersection cannot start before both intervals begin.
The overlap ends at:
min(first.end, second.end)
because the intersection cannot continue after either interval ends. 6. Check whether the intervals actually overlap.
If:
overlap_start <= overlap_end
then a valid intersection exists, and we append it to the result. 7. Advance the pointer for the interval that ends first.
If first.end < second.end, increment i.
Otherwise, increment j.
This is the crucial optimization. The interval that ends first cannot overlap any future intervals from the other list. 8. Repeat until one pointer reaches the end of its list.
Why it works
The algorithm maintains the invariant that all intersections involving intervals before pointers i and j have already been processed completely.
At every step, we compare the only pair of intervals that could currently overlap. After processing them, the interval with the smaller endpoint can never overlap future intervals because future intervals start later due to sorted order. Advancing that pointer therefore never skips a valid intersection.
Since every interval is processed at most once, the algorithm correctly finds all intersections in linear time.
Python Solution
from typing import List
class Solution:
def intervalIntersection(
self,
firstList: List[List[int]],
secondList: List[List[int]]
) -> List[List[int]]:
i = 0
j = 0
intersections = []
while i < len(firstList) and j < len(secondList):
first_start, first_end = firstList[i]
second_start, second_end = secondList[j]
overlap_start = max(first_start, second_start)
overlap_end = min(first_end, second_end)
if overlap_start <= overlap_end:
intersections.append([overlap_start, overlap_end])
if first_end < second_end:
i += 1
else:
j += 1
return intersections
The implementation begins by initializing two pointers, one for each interval list. These pointers always represent the current intervals under consideration.
Inside the loop, the current intervals are unpacked into readable variable names. This improves clarity and makes the overlap logic easier to follow.
The overlap calculation directly mirrors the mathematical definition of interval intersection:
- The overlap starts at the larger starting value
- The overlap ends at the smaller ending value
If the computed start is less than or equal to the computed end, the intervals overlap and the intersection is appended to the result list.
Finally, the algorithm advances the pointer belonging to the interval that ends first. This ensures we never revisit intervals that can no longer produce intersections.
The loop continues until one list is fully processed.
Go Solution
func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
i := 0
j := 0
result := [][]int{}
for i < len(firstList) && j < len(secondList) {
firstStart := firstList[i][0]
firstEnd := firstList[i][1]
secondStart := secondList[j][0]
secondEnd := secondList[j][1]
overlapStart := max(firstStart, secondStart)
overlapEnd := min(firstEnd, secondEnd)
if overlapStart <= overlapEnd {
result = append(result, []int{overlapStart, overlapEnd})
}
if firstEnd < secondEnd {
i++
} else {
j++
}
}
return result
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
The Go implementation follows the same logic as the Python version, but there are a few language-specific details worth noting.
Go does not provide built-in min and max functions for integers, so helper functions are implemented manually.
The result is stored in a slice of integer slices, [][]int. Each intersection interval is appended dynamically as overlaps are discovered.
Go slices naturally handle both empty and populated results, so no special handling is needed for empty outputs.
Integer overflow is not a concern because the interval bounds fit comfortably within Go's standard integer range.
Worked Examples
Example 1
Input:
firstList = [[0,2],[5,10],[13,23],[24,25]]
secondList = [[1,5],[8,12],[15,24],[25,26]]
| Step | firstList[i] | secondList[j] | Overlap Start | Overlap End | Intersection? | Pointer Move |
|---|---|---|---|---|---|---|
| 1 | [0,2] | [1,5] | 1 | 2 | Yes → [1,2] | Move i |
| 2 | [5,10] | [1,5] | 5 | 5 | Yes → [5,5] | Move j |
| 3 | [5,10] | [8,12] | 8 | 10 | Yes → [8,10] | Move i |
| 4 | [13,23] | [8,12] | 13 | 12 | No | Move j |
| 5 | [13,23] | [15,24] | 15 | 23 | Yes → [15,23] | Move i |
| 6 | [24,25] | [15,24] | 24 | 24 | Yes → [24,24] | Move j |
| 7 | [24,25] | [25,26] | 25 | 25 | Yes → [25,25] | Move i |
Final result:
[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Example 2
Input:
firstList = [[1,3],[5,9]]
secondList = []
Since secondList is empty, the loop condition immediately fails.
No intersections are possible.
Result:
[]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n + m) | Each interval is processed at most once |
| Space | O(1) excluding output | Only pointer variables are used |
The algorithm is linear because each pointer moves forward monotonically and never moves backward. Each interval from both lists is visited at most once.
The auxiliary space usage is constant because we only store a few variables regardless of input size. The output list itself is not counted toward auxiliary space complexity.
Test Cases
from typing import List
class Solution:
def intervalIntersection(
self,
firstList: List[List[int]],
secondList: List[List[int]]
) -> List[List[int]]:
i = 0
j = 0
intersections = []
while i < len(firstList) and j < len(secondList):
first_start, first_end = firstList[i]
second_start, second_end = secondList[j]
overlap_start = max(first_start, second_start)
overlap_end = min(first_end, second_end)
if overlap_start <= overlap_end:
intersections.append([overlap_start, overlap_end])
if first_end < second_end:
i += 1
else:
j += 1
return intersections
solution = Solution()
# Provided example
assert solution.intervalIntersection(
[[0,2],[5,10],[13,23],[24,25]],
[[1,5],[8,12],[15,24],[25,26]]
) == [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
# One list empty
assert solution.intervalIntersection(
[[1,3],[5,9]],
[]
) == []
# Both lists empty
assert solution.intervalIntersection(
[],
[]
) == []
# No overlap at all
assert solution.intervalIntersection(
[[1,2],[5,6]],
[[3,4],[7,8]]
) == []
# Single point overlap
assert solution.intervalIntersection(
[[1,5]],
[[5,10]]
) == [[5,5]]
# One interval completely inside another
assert solution.intervalIntersection(
[[1,10]],
[[3,5]]
) == [[3,5]]
# Multiple overlaps with one large interval
assert solution.intervalIntersection(
[[1,100]],
[[2,3],[4,5],[50,60]]
) == [[2,3],[4,5],[50,60]]
# Identical intervals
assert solution.intervalIntersection(
[[1,5],[10,15]],
[[1,5],[10,15]]
) == [[1,5],[10,15]]
# Adjacent but non-overlapping intervals
assert solution.intervalIntersection(
[[1,2]],
[[3,4]]
) == []
# Large boundary values
assert solution.intervalIntersection(
[[0,1000000000]],
[[999999999,1000000000]]
) == [[999999999,1000000000]]
| Test | Why |
|---|---|
| Standard example | Validates normal multi-interval behavior |
| One list empty | Ensures early termination works |
| Both lists empty | Confirms empty input handling |
| No overlap | Verifies non-overlapping intervals are ignored |
| Single point overlap | Tests closed interval behavior |
| Nested interval | Ensures containment works correctly |
| One large interval vs many small | Tests repeated overlap behavior |
| Identical intervals | Confirms exact matching intervals |
| Adjacent non-overlapping | Ensures strict overlap logic |
| Large values | Validates boundary constraints |
Edge Cases
Empty Input Lists
One or both lists may be empty. This is a common source of bugs because some implementations assume at least one interval exists.
The current implementation handles this naturally through the loop condition:
while i < len(firstList) and j < len(secondList):
If either list is empty, the loop never executes and an empty result is returned immediately.
Single Point Intersections
Because intervals are closed, endpoints count as valid overlaps.
For example:
[1,5] and [5,10]
intersect at:
[5,5]
A common mistake is using:
overlap_start < overlap_end
instead of:
overlap_start <= overlap_end
The implementation correctly includes single-point intersections.
One Interval Fully Contains Another
An interval from one list may completely contain an interval from the other list.
Example:
[1,10] and [3,5]
The overlap logic still works correctly because:
max(1,3) = 3
min(10,5) = 5
producing [3,5].
The pointer advancement logic also remains correct because the shorter interval ends first and is safely discarded afterward.