Interval List Intersections

MediumProblemExternal linkUpdated Oct 25, 2026

Description

You get two lists of closed intervals, firstList and secondList. Each list is sorted, and no two intervals in the same list overlap or touch. Return every interval of time that is in both lists, in order.

A closed interval [a, b] includes both a and b, so two intervals that touch share a single point: [1, 5] and [5, 9] share [5, 5].

Examples

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]]

Explanation: [0, 2] and [1, 5] share [1, 2]; [5, 10] touches [1, 5] at 5 and shares [8, 10] with [8, 12]; and so on. Touching ends count, because the intervals are closed.

Example 2

Input: firstList = [[1, 3], [5, 9]], secondList = []

Output: []

Explanation: The second list is empty, so nothing is in both.

Constraints

0 ≤ firstList.length, secondList.length ≤ 1000
firstList.length + secondList.length ≥ 1
0 ≤ start < end ≤ 10^9 for every interval
In each list, every interval ends before the next one starts

Editorial

Brute Force

Intuition

Every piece of time that's in both lists lies inside one interval of each. So check every pair: two intervals share [the later start, the earlier end], as long as that isn't empty. Since both lists are sorted, the pieces come out in order.

Step-by-Step Explanation

Let's take firstList = [[1, 4], [6, 9], [11, 14]] and secondList = [[2, 7], [9, 12]]:

[1, 4] and [2, 7] share [2, 4].
[1, 4] and [9, 12] share nothing, because [1, 4] ends before the other starts.
[6, 9] and [2, 7] share [6, 7].
[6, 9] and [9, 12] share [9, 9].
[11, 14] and [2, 7] share nothing, because [2, 7] ends before the other starts.
[11, 14] and [9, 12] share [11, 12].
All 6 pairs checked, and 2 of them shared nothing. The answer is [[2, 4], [6, 7], [9, 9], [11, 12]].

Check Every Pair — firstList on top, secondList below; the current pair is indigo, and the shaded band is what they share. The chips are the intersections found so far.

Algorithm

For each interval a in firstList and each b in secondList, take lo = max(a[0], b[0]) and hi = min(a[1], b[1]).
If lo ≤ hi, add [lo, hi].
Return the list.

Code

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        vector<vector<int>> out;
        for (const auto& a : firstList)                  // every pair, one from each list
            for (const auto& b : secondList) {
                int lo = max(a[0], b[0]), hi = min(a[1], b[1]);
                if (lo <= hi) out.push_back({lo, hi});   // they share [lo, hi]
            }
        return out;                                      // already in order: both lists are sorted
    }
};

class Solution:
    def intervalIntersection(self, firstList: list[list[int]], secondList: list[list[int]]) -> list[list[int]]:
        out = []
        for a in firstList:                         # every pair, one from each list
            for b in secondList:
                lo, hi = max(a[0], b[0]), min(a[1], b[1])
                if lo <= hi:                        # they share [lo, hi]
                    out.append([lo, hi])
        return out                                  # already in order: both lists are sorted

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> out = new ArrayList<>();
        for (int[] a : firstList)                        // every pair, one from each list
            for (int[] b : secondList) {
                int lo = Math.max(a[0], b[0]), hi = Math.min(a[1], b[1]);
                if (lo <= hi) out.add(new int[]{lo, hi});   // they share [lo, hi]
            }
        return out.toArray(new int[0][]);                // already in order: both lists are sorted
    }
}

var intervalIntersection = function(firstList, secondList) {
    const out = [];
    for (const a of firstList)                       // every pair, one from each list
        for (const b of secondList) {
            const lo = Math.max(a[0], b[0]), hi = Math.min(a[1], b[1]);
            if (lo <= hi) out.push([lo, hi]);        // they share [lo, hi]
        }
    return out;                                      // already in order: both lists are sorted
};

Complexity Analysis

Time Complexity: O(m · n)

Every pair is checked once.

Space Complexity: O(1)

Besides the answer.

Why This Approach Is Not Efficient

It passes here, since at most 1,000 × 1,000 = 1,000,000 pairs are checked. But most pairs are far apart and can't share anything: even in the small example, 2 of the 6 pairs found nothing. With 100,000 intervals in each list that's 10 billion pairs, while the walk below takes at most 200,000 steps.

Optimal Approach - Two Pointers

Intuition

Keep one index in each list and look only at the two current intervals. After recording what they share, one of them is done: the one that ends first. Say firstList's interval ends first, at time t. secondList's current interval ends at t or later, and its next one starts after that, so after t. The finished interval can't reach it, or anything after it. Move past it and compare again.

Each step moves one index forward, so the walk ends after at most m + n steps.

Step-by-Step Explanation

Let's take the same lists:

[1, 4] and [2, 7] share [2, 4]. [1, 4] ends first, at 4, so it's done. Move on in firstList.
[6, 9] and [2, 7] share [6, 7]. [2, 7] ends first, at 7, so it's done. Move on in secondList.
[6, 9] and [9, 12] share [9, 9]. [6, 9] ends first, at 9, so it's done. Move on in firstList.
[11, 14] and [9, 12] share [11, 12]. [9, 12] ends first, at 12, so it's done. Move on in secondList.
One list ran out after 4 steps, one per interval passed. The answer is [[2, 4], [6, 7], [9, 9], [11, 12]].

Move Past the One That Ends First — The current interval of each list is indigo, and passed ones fade. The shaded band is what the current pair shares.

Algorithm

Start with i = 0 and j = 0.
While both lists have intervals left, record [max of the starts, min of the ends] if it isn't empty.
Move i if firstList[i] ends first, else move j.
Return the list.

Code

class Solution {
public:
    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({lo, hi});             // they share [lo, hi]
            if (firstList[i][1] < secondList[j][1]) i++;       // the one that ends first can't reach anything later
            else j++;
        }
        return out;
    }
};

class Solution:
    def intervalIntersection(self, firstList: list[list[int]], secondList: list[list[int]]) -> list[list[int]]:
        i = j = 0
        out = []
        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:                            # they share [lo, hi]
                out.append([lo, hi])
            if firstList[i][1] < secondList[j][1]:  # the one that ends first can't reach anything later
                i += 1
            else:
                j += 1
        return out

class Solution {
    public 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});          // they share [lo, hi]
            if (firstList[i][1] < secondList[j][1]) i++;       // the one that ends first can't reach anything later
            else j++;
        }
        return out.toArray(new int[0][]);
    }
}

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]);           // they share [lo, hi]
        if (firstList[i][1] < secondList[j][1]) i++;   // the one that ends first can't reach anything later
        else j++;
    }
    return out;
};

Complexity Analysis

Time Complexity: O(m + n)

Every step passes one interval: 4 steps here, against 6 pairs.

Space Complexity: O(1)

Besides the answer.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Moving the one that starts first. if firstList[i][0] < secondList[j][0]:

On firstList = [[1, 10]], secondList = [[2, 3], [4, 5], [6, 7]] it returns [[2,3]]; the answer is [[2,3],[4,5],[6,7]]. The interval that starts first may still reach further than the other one. Only the one that ends first is sure to be done.

Moving both after a match. i += 1; j += 1

On firstList = [[1, 10]], secondList = [[2, 3], [4, 5], [6, 7]] it returns [[2,3]]; the answer is [[2,3],[4,5],[6,7]]. After a match, the interval that ends later may share more with the next interval of the other list. Move only the one that ends first.

Missing touching intervals. if lo < hi:

On firstList = [[1, 5]], secondList = [[5, 9]] it returns []; the answer is [[5,5]]. The intervals are closed, so two that touch share that one point: [1, 5] and [5, 9] share [5, 5]. Test lo <= hi.

Returning the union of each pair. out.append([min(a[0], b[0]), max(a[1], b[1])])

On firstList = [[1, 4]], secondList = [[2, 7]] it returns [[1,7]]; the answer is [[2,4]]. What two intervals share runs from the later start to the earlier end. The earlier start and the later end cover both of them, which is the union.

Where This Pattern Is Taught

Two pointers over two sorted interval lists are taught in Introduction to Intervals, along with the overlap test and merging.