Problem statement

You are given two lists of closed intervals, each sorted and pairwise disjoint. Return the intersection of the two lists — every interval common to both.

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 <= list lengths <= 12
• 0 <= start <= end <= 100
• Each list is sorted and disjoint.

Hints for Interval List Intersections

1. Hint 1

   Two pointers: intersect the current pair as [max(starts), min(ends)].

2. Hint 2

   Advance the pointer of the interval that ends first.

How to solve Interval List Intersections

Two intervals overlap in [max(starts), min(ends)] — that formula is the whole computation. The only question is which pairs to test, and because both lists are sorted and internally disjoint, a two-pointer walk visits every pair that could possibly intersect while skipping the rest.

Approach

1. Point i at the first interval of firstList and j at the first of secondList.
2. Compute the candidate overlap: lo = max(a[i][0], b[j][0]) and hi = min(a[i][1], b[j][1]).
3. If lo <= hi, that is a real intersection — record [lo, hi].
4. Advance the pointer whose interval ends first; it can never intersect anything later in the other list.
5. Stop when either list runs out.

Why it works

The interval that ends first is finished with: every remaining interval in the other list starts at or after the current one, and they only move rightwards, so nothing further can reach back before its end. Discarding it therefore loses no intersections, and each step consumes one interval — giving a single linear pass over both lists combined. The lo <= hi test is exactly the condition for the candidate range to be non-empty.

Complexity

• Time — O(n + m)
• Space — O(n + m)

Pitfalls

• The intervals are closed, so a single shared endpoint counts: the test is lo <= hi, and [5,5] is a legitimate result.
• Advance based on which interval ends first, not on which starts first.
• Either list may be empty — the loop must simply not run.
• Advance exactly one pointer per iteration; advancing both can skip a valid intersection.

Reference solution

Python

from typing import List

def intervalIntersection(firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
    out = []
    i = j = 0
    while i < len(firstList) and j < len(secondList):
        lo = max(firstList[i][0], secondList[j][0])
        hi = min(firstList[i][1], secondList[j][1])
        if lo <= hi:
            out.append([lo, hi])
        if firstList[i][1] < secondList[j][1]:
            i += 1
        else:
            j += 1
    return out

Java

public static int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
    List<int[]> out = new ArrayList<>();
    int i = 0, j = 0;
    while (i < firstList.length && j < secondList.length) {
        int lo = Math.max(firstList[i][0], secondList[j][0]);
        int hi = Math.min(firstList[i][1], secondList[j][1]);
        if (lo <= hi) out.add(new int[]{lo, hi});
        if (firstList[i][1] < secondList[j][1]) i++;
        else j++;
    }
    return out.toArray(new int[0][]);
}

C++

vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
    vector<vector<int>> out;
    size_t i = 0, j = 0;
    while (i < firstList.size() && j < secondList.size()) {
        int lo = max(firstList[i][0], secondList[j][0]);
        int hi = min(firstList[i][1], secondList[j][1]);
        if (lo <= hi) out.push_back(vector<int>{lo, hi});
        if (firstList[i][1] < secondList[j][1]) i++;
        else j++;
    }
    return out;
}

JavaScript

var intervalIntersection = function(firstList, secondList) {
    const out = [];
    let i = 0, j = 0;
    while (i < firstList.length && j < secondList.length) {
        const lo = Math.max(firstList[i][0], secondList[j][0]);
        const hi = Math.min(firstList[i][1], secondList[j][1]);
        if (lo <= hi) out.push([lo, hi]);
        if (firstList[i][1] < secondList[j][1]) i++;
        else j++;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium