What is the brute force approach and complexity for Interval List Intersections?

Compare every interval of the first list with every interval of the second with time complexity O(M · N) and space complexity O(1).

What is the optimal approach and complexity for Interval List Intersections?

Walk both lists together; output the overlap, then advance the interval that ends first with optimal time complexity O(M + N) and space complexity O(1).

How do you identify the pattern for Interval List Intersections?

Look for key signals in the prompt: "two lists, each sorted and disjoint" indicates Walk both lists together with one pointer each, like merging two sorted arrays.; "intersection" indicates The overlap of two intervals is [max of starts, min of ends], if that range isn't empty.; "closed intervals" indicates Ends are included, so the test is lo ≤ hi and a single point [x, x] counts..

Interval List Intersections

Medium·LeetCode #986Basic Anchor

LeetCode

Jump:

30-Second Mental ModelIntervals — Intersection of two lists (two pointers)

Complexity:O(M · N)→O(M + N)

Key Insight

Keep i in the first list and j in the second. Compute lo = max(starts) and hi = min(ends). If lo ≤ hi, add [lo, hi]. Then move past the interval that ends first. It can't overlap anything else, because everything later in the other list starts after the other current interval ends.

Core Validity Invariant

Two closed intervals overlap exactly when lo = max(starts) ≤ hi = min(ends), and then the overlap is [lo, hi].

Problem

You get two lists of closed intervals, firstList and secondList. A closed interval [a, b] means every number from a to b, including both ends.

Inside each list, the intervals are sorted and don't overlap or touch each other.

Return every place where the two lists overlap, as a list of intervals in order. If two intervals only share one point, that point counts as an interval [x, x].

Input

Two lists of intervals firstList and secondList, where each interval is [start, end].

Output

A list of intervals: the intersection of the two lists, sorted by start. It can be empty.

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

[0,2] and [1,5] share [1,2]. [5,10] and [1,5] share only the point 5, so [5,5]. [24,25] and [15,24] share only 24, and [24,25] and [25,26] share only 25.

Example 2

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

Output: []

The second list is empty, so nothing overlaps.

Constraints

• 0 ≤ firstList.length, secondList.length ≤ 1000
• firstList.length + secondList.length ≥ 1
• 0 ≤ start < end ≤ 10^9
• Within one list: end of one interval < start of the next

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Given just two intervals, how do I find the part they share? When do they share nothing?
2.
Is touching at one point an overlap here? What does "closed" tell me?
3.
Both lists are sorted. Does that remind me of another problem where I walk two sorted lists at once?
4.
After comparing one interval from each list, which of the two can never overlap anything else?
5.
How many comparisons do I really need if I never go backwards?

Brute force approach

Idea

Take every pair (a, b) with a from the first list and b from the second. Their overlap is [max(starts), min(ends)]. If lo ≤ hi, add it. Because both lists are sorted and their intervals don't overlap, the pieces come out already in order.

Thinking process

1
Any piece of the answer is the overlap of one interval from each list. So if I try every pair, I can't miss anything.
2
For one pair, the overlap starts at the later start and ends at the earlier end.
3
If the later start is after the earlier end, they don't overlap.
4
The order works out on its own: for a fixed a, its pieces come in the order of the second list, and pieces from a later a are further right.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        vector<vector<int>> result;
        // Try every pair (one interval from each list).
        // Both lists are sorted and disjoint, so the pieces come out already in order.
        for (auto& a : firstList) {
            for (auto& b : secondList) {
                int lo = max(a[0], b[0]);  // the later start
                int hi = min(a[1], b[1]);  // the earlier end
                if (lo <= hi) {            // closed intervals: a single point counts
                    result.push_back({lo, hi});
                }
            }
        }
        return result;
    }
};

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> result = new ArrayList<>();
        // Try every pair (one interval from each list).
        // Both lists are sorted and disjoint, so the pieces come out already in order.
        for (int[] a : firstList) {
            for (int[] b : secondList) {
                int lo = Math.max(a[0], b[0]); // the later start
                int hi = Math.min(a[1], b[1]); // the earlier end
                if (lo <= hi) { // closed intervals: a single point counts
                    result.add(new int[] { lo, hi });
                }
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

class Solution:
    def intervalIntersection(
        self, firstList: list[list[int]], secondList: list[list[int]]
    ) -> list[list[int]]:
        result: list[list[int]] = []
        # Try every pair (one interval from each list).
        # Both lists are sorted and disjoint, so the pieces come out already in order.
        for a in firstList:
            for b in secondList:
                lo = max(a[0], b[0])  # the later start
                hi = min(a[1], b[1])  # the earlier end
                if lo <= hi:  # closed intervals: a single point counts
                    result.append([lo, hi])
        return result

export function intervalIntersection(firstList: number[][], secondList: number[][]): number[][] {
    const result: number[][] = [];
    // Try every pair (one interval from each list).
    // Both lists are sorted and disjoint, so the pieces come out already in order.
    for (const a of firstList) {
        for (const b of secondList) {
            const lo = Math.max(a[0], b[0]); // the later start
            const hi = Math.min(a[1], b[1]); // the earlier end
            if (lo <= hi) { // closed intervals: a single point counts
                result.push([lo, hi]);
            }
        }
    }
    return result;
}

Complexity

Time O(M · N)Space O(1)

M and N are the list lengths. Every pair is checked, about 10^6 pairs for two lists of 1000. That passes here, but most pairs are far apart and can't possibly overlap. The output list is not counted as extra space.

Optimized approach

Idea

Start from brute force

Brute force compares every interval of the first list with every interval of the second, even ones that are far apart.

Find the repeated work

Most pairs can't overlap. Once an interval from one list has ended, every later interval of the other list is too far right to touch it, yet brute force still checks them.

Define the state — what variables do I need?

i: The current interval in firstList. Everything before it is finished.
j: The current interval in secondList. Everything before it is finished.
lo, hi: lo = max of the two starts, hi = min of the two ends: the shared part of A[i] and B[j], if any.
result: The overlaps found so far, already in order.

Define validity

Two closed intervals overlap exactly when lo = max(starts) ≤ hi = min(ends), and then the overlap is [lo, hi].

Define the transitions — when does each pointer move, and why is it safe?

lo ≤ hi

result.push_back({lo, hi})

Both intervals cover every time from lo to hi. Closed intervals include their ends, so lo == hi is a real one-point overlap.

firstList[i] ends before secondList[j]

i++

The next interval of secondList starts after B[j] ends, and A[i] is over before that. So A[i] can't overlap anything else. B[j] keeps going and may still overlap A[i+1].

secondList[j] ends first, or both end together

j++

Same reason with the lists swapped. On a tie either move is fine: neither interval can overlap the other list's next interval.

What does the current window add to the answer?

Each step adds at most one piece: the overlap of the current two intervals. Pieces come out from left to right, so the result is sorted without any extra work.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        vector<vector<int>> result;
        int i = 0, j = 0;
        while (i < (int)firstList.size() && j < (int)secondList.size()) {
            int lo = max(firstList[i][0], secondList[j][0]);  // the later start
            int hi = min(firstList[i][1], secondList[j][1]);  // the earlier end
            if (lo <= hi) {
                result.push_back({lo, hi});
            }
            // The interval that ends first can't touch anything further right
            // in the other list, so it is finished. Move past it.
            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        return result;
    }
};

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int j = 0;
        while (i < firstList.length && j < secondList.length) {
            int lo = Math.max(firstList[i][0], secondList[j][0]); // the later start
            int hi = Math.min(firstList[i][1], secondList[j][1]); // the earlier end
            if (lo <= hi) {
                result.add(new int[] { lo, hi });
            }
            // The interval that ends first can't touch anything further right
            // in the other list, so it is finished. Move past it.
            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

class Solution:
    def intervalIntersection(
        self, firstList: list[list[int]], secondList: list[list[int]]
    ) -> list[list[int]]:
        result: list[list[int]] = []
        i, j = 0, 0
        while i < len(firstList) and j < len(secondList):
            lo = max(firstList[i][0], secondList[j][0])  # the later start
            hi = min(firstList[i][1], secondList[j][1])  # the earlier end
            if lo <= hi:
                result.append([lo, hi])
            # The interval that ends first can't touch anything further right
            # in the other list, so it is finished. Move past it.
            if firstList[i][1] < secondList[j][1]:
                i += 1
            else:
                j += 1
        return result

export function intervalIntersection(firstList: number[][], secondList: number[][]): number[][] {
    const result: number[][] = [];
    let i = 0;
    let j = 0;
    while (i < firstList.length && j < secondList.length) {
        const lo = Math.max(firstList[i][0], secondList[j][0]); // the later start
        const hi = Math.min(firstList[i][1], secondList[j][1]); // the earlier end
        if (lo <= hi) {
            result.push([lo, hi]);
        }
        // The interval that ends first can't touch anything further right
        // in the other list, so it is finished. Move past it.
        if (firstList[i][1] < secondList[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    return result;
}

Complexity

Time O(M + N)Space O(1)

Every step moves i or j forward, so there are at most M + N steps. The output list is not counted as extra space.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Compare every interval of the first list with every interval of the second	O(M · N)	O(1)
Optimal	Walk both lists together; output the overlap, then advance the interval that ends first	O(M + N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“two lists, each sorted and disjoint”Walk both lists together with one pointer each, like merging two sorted arrays.
“intersection”The overlap of two intervals is [max of starts, min of ends], if that range isn't empty.
“closed intervals”Ends are included, so the test is lo ≤ hi and a single point [x, x] counts.

Two sorted interval lists+overlap = [max start, min end]+drop the one that ends first→Intervals — Intersection of two lists (two pointers)

This is the anchor of the sub-pattern. Unlike Merge Intervals, we don't combine intervals from one list. We look at two lists and keep only the time that both cover. The whole idea is one rule: output the overlap, then advance the one that ends first. Meeting Scheduler and Employee Free Time reuse this walk.

Don't make this mistake

Advancing both pointers every step

✗ if (lo <= hi) result.push_back({lo, hi}); i++; j++;

✓ if (firstList[i][1] < secondList[j][1]) i++; else j++;

The interval that ends later may still overlap the next interval of the other list. With [[0,10]] and [[1,2],[5,6]], moving both after the first overlap loses [5,6].

Advancing the one with the larger end

✗ if (firstList[i][1] > secondList[j][1]) i++;

✓ if (firstList[i][1] < secondList[j][1]) i++;

The interval with the larger end is the one that can still reach more of the other list. Drop the one that ends first, because it is the one that is finished.

Using lo < hi and losing single points

✗ if (lo < hi) result.push_back({lo, hi});

✓ if (lo <= hi) result.push_back({lo, hi});

The intervals are closed, so [5,10] and [1,5] both include time 5. The answer must include [5,5].

Pattern confusion: merging instead of intersecting

This is not Merge Intervals. Putting both lists together, sorting and merging gives the union (time covered by either list). We want the time covered by both. Also, sorting would waste the fact that both lists are already sorted. Two pointers do it in O(M + N).

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Intervals translate into production architectures and low-level memory mechanics.

LLD Architecture