Interval List Intersections solution and explanation
Google
9 more videos on this problem
Interval List Intersections | Leetcode #986Techdose · 12:19 · 29K views
INTERVAL LIST INTERSECTIONS | LEETCODE 986 | PYTHON TWO-POINTER SOLUTIONCracking FAANG · 12:16 · 8K views
Leetcode 986. Interval List Intersections [Algo + Code + Time/Space Complexity]jayati tiwari · 10:13 · 5K views
INTERVAL LIST INTERSECTIONS | LeetCode 986 | Hindi SolutionPepcoding · 32:53 · 5K views
Interval List Intersections | LeetCode 986 | C++, Java, Python | May LeetCoding Day 23Knowledge Center · 24:07 · 2K views
Interval List Intersections - LeetCode 986 - Python #leetcode #intervalsDeepti Talesra · 15:42 · 2K views
[Java] Leetcode 986. Interval List Intersections [Intervals #5]Eric Programming · 15:27 · 2K views
Interval List Intersections | leetcode 986 | HindiCodebix · 16:51 · 1K views
Leetcode - Interval List Intersections (Python)Timothy H Chang · 7:54 · 1K views
Interval List Intersections | Leetcode 986 | Live coding session 🔥🔥🔥🔥Coding Decoded · 12:28 · 770 views
The problem
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.
def intervalIntersection(firstList, secondList):
i, j = 0, 0
result = []
while i < len(firstList) and j < len(secondList):
start = max(firstList[i][0], secondList[j][0])
end = min(firstList[i][1], secondList[j][1])
if start <= end:
result.append([start, end])
if firstList[i][1] < secondList[j][1]:
i += 1
else:
j += 1
return resultimport java.util.*;
class Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
List<int[]> result = new ArrayList<>();
int i = 0, j = 0;
while (i < firstList.length && j < secondList.length) {
int start = Math.max(firstList[i][0], secondList[j][0]);
int end = Math.min(firstList[i][1], secondList[j][1]);
if (start <= end) {
result.add(new int[]{start, end});
}
if (firstList[i][1] < secondList[j][1])
i++;
else
j++;
}
return result.toArray(new int[result.size()][]);
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
vector<vector<int>> result;
int i = 0, j = 0;
while (i < A.size() && j < B.size()) {
int start = max(A[i][0], B[j][0]);
int end = min(A[i][1], B[j][1]);
if (start <= end) {
result.push_back({ start, end });
}
if (A[i][1] < B[j][1])
i++;
else
j++;
}
return result;
}var intervalIntersection = function(firstList, secondList) {
let i = 0, j = 0;
const result = [];
while (i < firstList.length && j < secondList.length) {
let start = Math.max(firstList[i][0], secondList[j][0]);
let end = Math.min(firstList[i][1], secondList[j][1]);
if (start <= end) {
result.push([start, end]);
}
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
int** intervalIntersection(int** A, int ASize, int* AColSize, int** B, int BSize, int* BColSize, int* returnSize, int** returnColumnSizes){
int a = 0, b = 0;
int capacity = 1000; // Initial capacity based on constraints
int** ans = (int**) malloc(sizeof(int*) * capacity);
*returnColumnSizes = (int*) malloc(sizeof(int) * capacity);
*returnSize = 0;
while (a < ASize && b < BSize) {
int start = fmax(A[a][0], B[b][0]);
int end = fmin(A[a][1], B[b][1]);
if (start <= end) {
if (*returnSize == capacity) {
capacity *= 2;
ans = (int**) realloc(ans, sizeof(int*) * capacity);
*returnColumnSizes = (int*) realloc(*returnColumnSizes, sizeof(int) * capacity);
}
ans[*returnSize] = (int*) malloc(sizeof(int) * 2);
ans[*returnSize][0] = start;
ans[*returnSize][1] = end;
(*returnColumnSizes)[*returnSize] = 2;
(*returnSize)++;
}
if (A[a][1] < B[b][1])
a++;
else
b++;
}
return ans;
}using System;
using System.Collections.Generic;
public class Solution {
public int[][] IntervalIntersection(int[][] firstList, int[][] secondList) {
List<int[]> result = new List<int[]>();
int i = 0, j = 0;
while (i < firstList.Length && j < secondList.Length) {
int start = Math.Max(firstList[i][0], secondList[j][0]);
int end = Math.Min(firstList[i][1], secondList[j][1]);
if (start <= end) {
result.Add(new int[] {start, end});
}
if (firstList[i][1] < secondList[j][1])
i++;
else
j++;
}
return result.ToArray();
}
}The function iterates through both lists with two indexes, i and j. It calculates potential intersections, adds valid intersections to the result, and advances the pointer of the interval with the smaller endpoint to discover new intersections.
Time Complexity: O(n + m), where n and m are the lengths of the two lists, as each interval is processed once.
Space Complexity: O(1), additional to the output list.
Approach 2: Default Approach
function intervalIntersection(firstList: number[][], secondList: number[][]): number[][] {
const n = firstList.length;
const m = secondList.length;
const res = [];
let i = 0;
let j = 0;
while (i < n && j < m) {
const start = Math.max(firstList[i][0], secondList[j][0]);
const end = Math.min(firstList[i][1], secondList[j][1]);
if (start <= end) {
res.push([start, end]);
}
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
}
return res;
}func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
m, n := len(firstList), len(secondList)
var ans [][]int
for i, j := 0, 0; i < m && j < n; {
l := max(firstList[i][0], secondList[j][0])
r := min(firstList[i][1], secondList[j][1])
if l <= r {
ans = append(ans, []int{l, r})
}
if firstList[i][1] < secondList[j][1] {
i++
} else {
j++
}
}
return ans
}impl Solution {
pub fn interval_intersection(
first_list: Vec<Vec<i32>>,
second_list: Vec<Vec<i32>>,
) -> Vec<Vec<i32>> {
let n = first_list.len();
let m = second_list.len();
let mut res = Vec::new();
let (mut i, mut j) = (0, 0);
while i < n && j < m {
let start = first_list[i][0].max(second_list[j][0]);
let end = first_list[i][1].min(second_list[j][1]);
if start <= end {
res.push(vec![start, end]);
}
if first_list[i][1] < second_list[j][1] {
i += 1;
} else {
j += 1;
}
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointers Technique | Time Complexity: O(n + m), where n and m are the lengths of the two lists, as each interval is processed once. Space Complexity: O(1), additional to the output list. |
| Default Approach | – |
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 |
Frequently asked questions
Is Interval List Intersections easy or hard?
Interval List Intersections is considered a medium-level problem. The main challenge is recognizing that sorted intervals allow a linear two-pointer scan instead of brute force comparisons.
How to solve Interval List Intersections in O(n)?
Use a two-pointer scan across both sorted interval lists. For intervals A[i] and B[j], compute the overlap using max(start) and min(end). If they intersect, record the result. Move the pointer that has the smaller ending value. This ensures each interval is processed once, giving O(n + m) runtime.
What is the best approach for Interval List Intersections?
The optimal approach uses the two pointers technique. Since both interval lists are sorted, you can scan them simultaneously and compare one interval from each list at a time. By advancing the pointer of the interval that ends first, the algorithm processes each interval once, achieving O(n + m) time complexity and O(1) extra space.
Is Interval List Intersections asked at Google/Amazon/Meta?
Interval-based problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variations involving interval merging, overlap detection, and scheduling are common because they test two-pointer reasoning and edge-case handling.
What data structure is used in Interval List Intersections?
The problem mainly uses arrays (or lists) of intervals. The algorithm relies on pointer indices to traverse both arrays and compute overlaps using simple arithmetic comparisons between interval boundaries.
What is the time complexity of Interval List Intersections?
The optimal two-pointer solution runs in O(n + m) time, where n and m are the lengths of the two interval lists. Each pointer moves forward at most once per interval. The brute force method compares every pair and runs in O(n * m) time.
Interval List Intersections Python or Java solution approach?
Both Python and Java implementations follow the same logic. Maintain two indices for the interval lists, compute overlap with max(start) and min(end), append valid intersections, then advance the pointer with the smaller end value. The overall complexity remains O(n + m).