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 <= 109 endj < startj+1In #986 Interval List Intersections, you are given two lists of closed intervals that are individually sorted and non-overlapping. The goal is to find all intersections between intervals from the two lists. A key observation is that because both lists are already sorted, we can process them efficiently using the two pointers technique.
Start with one pointer for each list. For the current intervals, compute the potential intersection using start = max(start1, start2) and end = min(end1, end2). If start <= end, the intervals overlap and this range forms a valid intersection. After processing, move the pointer belonging to the interval that finishes first, since that interval cannot intersect with later intervals in the other list.
This strategy ensures each interval is processed only once, giving a linear scan across both lists. The approach runs in O(n + m) time with O(1) extra space (excluding the result list).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers on Sorted Interval Lists | O(n + m) | O(1) auxiliary (excluding output) |
NeetCode
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int** intervalIntersection(int** A, int ASize, int* AColSize, 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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, interval-based problems are common in technical interviews at companies like Google, Amazon, and Facebook. This problem tests understanding of interval overlap logic and efficient two-pointer traversal.
The optimal approach uses the two pointers technique. Since both interval lists are sorted and non-overlapping internally, we can scan them simultaneously and compute overlaps using max start and min end. This results in linear time complexity.
Arrays or lists of intervals are sufficient for this problem. The key technique is pointer traversal rather than a specialized data structure, as the intervals are already sorted.
Because both interval lists are sorted by start time, the earliest finishing interval determines which pointer should move next. This guarantees that all possible intersections are checked without revisiting intervals.