Interval List Intersections - Solution & Explanation
Problem Statement
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.
The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].
Example 1:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Example 2:
Input: firstList = [[1,3],[5,9]], secondList = [] Output: []
Constraints:
0 <= firstList.length, secondList.length <= 1000firstList.length + secondList.length >= 10 <= starti < endi <= 109endi < starti+10 <= startj < endj <= 109endj < startj+1
Approach Overview
Problem Overview: You get two lists of closed intervals. Each list is already sorted and internally non-overlapping. The task is to return all intersections between intervals from the first list and the second list.
The challenge is efficiently identifying overlapping regions between two ordered interval sequences. Since both lists are sorted by start time, you can exploit that structure instead of comparing every pair.
Approach 1: Brute Force Comparison (O(n * m) time, O(1) space)
The straightforward solution compares every interval in the first list with every interval in the second list. For each pair [a1, a2] and [b1, b2], compute the overlap using start = max(a1, b1) and end = min(a2, b2). If start <= end, an intersection exists and should be added to the result.
This approach works because interval intersection can be determined in constant time. However, you still check all possible pairs using nested loops. With n intervals in the first list and m in the second, the time complexity becomes O(n * m). Space complexity remains O(1) excluding the output. This approach is easy to implement but inefficient for large inputs.
Approach 2: Two Pointers Technique (O(n + m) time, O(1) space)
A better solution uses the two pointers pattern to scan both interval lists simultaneously. Start with pointer i at the beginning of the first list and pointer j at the beginning of the second. At each step, compare intervals A[i] and B[j].
Compute the intersection exactly the same way as the brute force method: start = max(A[i][0], B[j][0]) and end = min(A[i][1], B[j][1]). If start <= end, add the interval to the result. After checking overlap, move the pointer that has the smaller end value. This works because the interval that ends first cannot intersect with any future intervals in the other list.
Each interval is processed at most once. That reduces the runtime to O(n + m), where n and m are the sizes of the two lists. The algorithm uses only a few variables, so the extra space complexity is O(1). This technique is common in ordered data problems involving arrays and interval merging.
Recommended for interviews: Interviewers typically expect the Two Pointers solution. Starting with the brute force approach shows you understand how interval overlap works. Then optimizing to the O(n + m) two-pointer scan demonstrates algorithmic thinking and awareness of sorted input properties.
Approach 1: Two Pointers Technique
In this approach, we use a two-pointer technique to traverse both lists of intervals simultaneously. We check for intersections between the intervals pointed by our two pointers. If there's an intersection, we record it. We then progress the pointer that points to the interval with the smaller endpoint. This ensures that we consider new overlapping possibilities as the intervals in each list are disjoint and sorted.
We use pointers a and b to iterate over firstList and secondList respectively. We find the maximum start and minimum end for the current intervals pointed by these pointers to determine overlap. If there's an overlap, it is added to the result list. We move the pointer with the smaller endpoint to ensure progress.
Complexity
Time Complexity: O(n + m), where n and m are the number of intervals in the two lists. This is because we process each interval at most once.
Space Complexity: O(1), apart from the output space, since only a few variables are used.
Approach 2: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Two Pointers Technique | Time Complexity: O(n + m), where n and m are the number of intervals in the two lists. This is because we process each interval at most once. Space Complexity: O(1), apart from the output space, since only a few variables are used. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n * m) | O(1) | Small inputs or when interval lists are not guaranteed to be sorted |
| Two Pointers Technique | O(n + m) | O(1) | Best choice when both interval lists are sorted and non-overlapping internally |
Video Solution
Interval List Intersections | Leetcode #986 • Techdose • 29,154 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Interval List Intersections easy or hard?
How to solve Interval List Intersections in O(n)?
What is the best approach for Interval List Intersections?
Is Interval List Intersections asked at Google/Amazon/Meta?
What data structure is used in Interval List Intersections?
What is the time complexity of Interval List Intersections?
Interval List Intersections Python or Java solution approach?
Ready to solve this problem?
Practice Interval List Intersections with our built-in code editor and test cases.
Practice on FleetCode