LeetCode · #986

Interval List Intersections Solution

Given two sorted lists of disjoint intervals, return their intersection.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #986

🏗️

Pattern

Intervals — two pointers

Given two lists of closed intervals, each sorted and disjoint, return the intersection of these two interval lists.

Example

Input: A = [[0,2],[5,10],[13,23],[24,25]]
         B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Constraints

• 0 ≤ firstList.length, secondList.length ≤ 1000 • Each list is sorted and disjoint

Section Two · Approach 1

Brute Force — O(m·n)

For each interval in A, check every interval in B for intersection.

Problem: O(m·n). Since both lists are sorted, use two pointers — advance the one that ends earlier. O(m+n).

Section Three · Approach 2

Two Pointers — O(m+n)

Pointer i for A, j for B. At each step, compute the intersection [max(start), min(end)]. If valid (start ≤ end), add it. Advance the pointer whose interval ends first (it can't intersect anything else from the other list).

💡 Mental model: Two timelines laid side by side. Two fingers walk along each. They find where the timelines overlap (max of starts, min of ends). Then the finger on the timeline that ends first moves to the next interval — the other timeline's interval might still overlap the next one.

Algorithm

i = 0, j = 0.
While i < m and j < n:
lo = max(A[i].start, B[j].start), hi = min(A[i].end, B[j].end).
If lo ≤ hi: add [lo, hi].
If A[i].end < B[j].end: i++. Else: j++.

🎯 When to recognize this pattern: "Intersect two sorted interval lists." Two pointers on sorted sequences — standard merge-like technique. The key decision: advance the pointer with the smaller end.

Section Four · Trace

Visual Walkthrough

Interval Intersections — Two Pointers

Section Five · Implementation

Code — Java & Python

Java — Two pointers

 import java.util.*;
class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
List<int[]> res = new ArrayList<>();
int i = 0, j = 0;
while (i < A.length && j < B.length) {
int lo = Math.max(A[i][0], B[j][0]);
int hi = Math.min(A[i][1], B[j][1]);
if (lo <= hi) res.add(new int[]{lo, hi});
if (A[i][1] < B[j][1]) i++;
else j++;
        }
return res.toArray(new int[res.size()][]);
    }
}

Python — Two pointers

 class Solution:
def intervalIntersection(self, A: list[list[int]], B: list[list[int]]) -> list[list[int]]:
        res, i, j = [], 0, 0 while i < len(A) and j < len(B):
            lo = max(A[i][0], B[j][0])
            hi = min(A[i][1], B[j][1])
if lo <= hi: res.append([lo, hi])
if A[i][1] < B[j][1]: i += 1 else: j += 1 return res

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Brute force	O(m·n)	O(m+n)
Two pointers ← optimal	O(m+n)	O(m+n) output

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty list	`A=[], B=[[1,2]]`	No intersection. Return [].
No overlap	`A=[[1,2]], B=[[3,4]]`	lo=3 > hi=2. No intersection.
Single point	`A=[[1,3]], B=[[3,5]]`	lo=3, hi=3 → [3,3] (single point interval).
One inside other	`A=[[1,10]], B=[[3,5]]`	Intersection = [3,5].

⚠ Common Mistake: Advancing both pointers when intervals have the same end. This can miss intersections. Only advance the one with the smaller end. If ends are equal, advancing either works (both are exhausted for future overlaps), but advancing only one is safer and simpler.

← Back to Interval problems

LearningTree

LC 986 · Interval List Intersections — Solution & Explanation | DSA Guide