Skip to main content
DSA patterns

Interval List Intersections

mediumTwo pointersAWSAzureGCPHashiCorp

Problem statement

You get two lists of intervals, firstList and secondList. Each list is already sorted by start value, and the intervals inside one list never overlap each other. Return every stretch of numbers that falls inside both an interval from firstList and an interval from secondList.

An interval [a, b] stands for every number from a to b, both ends included. Two intervals "intersect" where their ranges share numbers — for example [1, 3] and [2, 4] share the numbers 2 and 3, so their intersection is [2, 3]. Think of the two lists as two teams' booked maintenance windows: you want every stretch of time where both teams are already busy.

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: Compare each interval from firstList with the ones from secondList it could overlap. [0,2] and [1,5] share [1,2]; [5,10] and [1,5] share only the point [5,5], and [5,10] and [8,12] share [8,10]; [13,23] and [15,24] share [15,23]; [24,25] and [15,24] share only [24,24], and [24,25] and [25,26] share only [25,25].

Example 1

Example 2

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

Output: []

Explanation: secondList is empty, so there is nothing for firstList's intervals to intersect with.

Hints

Hint 1: Since both lists are already sorted and each list's own intervals never overlap, you never need to look backwards — one pointer per list, both only ever moving forward, is enough.

Approach

Optimal: Two pointers

Intuition

Both lists are already sorted, so you never need to jump backwards or compare an interval against every interval in the other list — a single pointer walking forward through each list is enough. At each step, look at the current interval from both lists and compute their overlap the same way as the brute-force approach. What decides which pointer to move next is whichever current interval finishes first: since it can't possibly reach any later interval in the other list either (its own list already ruled that out), it's done and the pointer for that list moves on.

Steps

  1. Set i = 0 and j = 0, one pointer into each list.
  2. While both pointers are still inside their lists: take the current interval from each, (aStart, aEnd) and (bStart, bEnd).
  3. Compute lo = max(aStart, bStart) and hi = min(aEnd, bEnd). If lo <= hi, add [lo, hi] to the result.
  4. Compare the two ends: if aEnd < bEnd, move i forward (that interval from firstList can't overlap anything further ahead); otherwise move j forward.
  5. Repeat until one pointer runs past the end of its list, then return the result.

Dry run

firstList = [[0,2],[5,10]], secondList = [[1,5],[8,12]]

i j current pair lo, hi overlap? move
0 0 [0,2] & [1,5] 1, 2 yes → [1,2] aEnd(2) < bEnd(5) → i++
1 0 [5,10] & [1,5] 5, 5 yes → [5,5] aEnd(10) < bEnd(5)? no → j++
1 1 [5,10] & [8,12] 8, 10 yes → [8,10] aEnd(10) < bEnd(12) → i++
2 1 i past the end of firstList — — loop stops

Result: [[1,2],[5,5],[8,10]] — same as the brute-force result, built in one pass instead of a nested one.

Edge cases: if either list is empty, the loop condition is false from the start and the result is empty (example 2). A single-point overlap like [5,5] is kept, since lo <= hi is still true when they're equal.

Complexity

Time O(n + m) - Each step of the loop advances one of the two pointers, and each pointer can advance at most n or m times, so the whole pass touches every interval once.

Space O(k) - Only the k intervals kept in the result; no extra structure is needed beyond two integer pointers.

from typing import List


class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        result = []
        i, j = 0, 0
        while i < len(firstList) and j < len(secondList):
            a_start, a_end = firstList[i]
            b_start, b_end = secondList[j]
            lo = max(a_start, b_start)
            hi = min(a_end, b_end)
            if lo <= hi:
                result.append([lo, hi])
            if a_end < b_end:
                i += 1
            else:
                j += 1
        return result


if __name__ == "__main__":
    print(Solution().intervalIntersection([[0, 2], [5, 10], [13, 23], [24, 25]], [[1, 5], [8, 12], [15, 24], [25, 26]]))
    print(Solution().intervalIntersection([[1, 3], [5, 9]], []))
RecapThe whole problem in a few lines, for the night before
  • Spot it: two sorted lists of non-overlapping intervals, find where they overlap
  • Idea: two pointers; the overlap is [max(starts), min(ends)] if start <= end; then advance the pointer whose interval ends first
  • Cost: O(m + n) time, O(1) extra space (output not counted)
  • Trap: advance the interval that ends first, not the one that starts first; touching at one point (end == start) still counts

Interview follow-ups

  • What if you also needed to know which pair of original intervals produced each overlap?

    Store the pair of indices (i, j) alongside each overlap instead of just [lo, hi]. The two-pointer walk already has both indices in hand at the moment it finds an overlap, so this needs no extra passes — just carry a little more information into the result.

  • The lists are far too large to hold in memory at once, but both are still sorted on disk.

    Read each list from disk as a stream, keeping only the current interval from each side in memory, the same way the two-pointer approach only looks at firstList[i] and secondList[j] at any moment. Advance whichever stream's current interval has the smaller end value, exactly as before — the algorithm's logic doesn't change, only where the intervals come from.

Frequently asked questions

Once you've compared an interval to its counterpart, the one with the smaller end value has already met the largest possible overlap it will ever get — every later interval in the other list starts even further along, past where this one already ends. So it can never contribute another overlap and is safe to retire, while the interval with the larger end value might still overlap the other list's next interval.

The problem defines a closed interval as including both endpoints, and it explicitly allows the intersection to be a single point rather than requiring a genuine range. [a, b] with a == b is still a valid closed interval — it just represents one number instead of a stretch of numbers.

No. The two pointers just stop as soon as either list runs out, so one list can be much longer or even empty (as in example 2) — the loop condition i < len(firstList) and j < len(secondList) handles that automatically.

Two independently maintained schedules — one team's deployment freeze windows and another team's maintenance windows, or two firewalls' allowed port ranges — are exactly two sorted, non-overlapping interval lists. Finding where they intersect answers "when are both teams blocked?" or "which ports are open on both sides?" without comparing every pair by hand.

Merge Intervals combines overlapping ranges from a single list into fewer, bigger ranges. This problem keeps two separate lists and finds where they overlap each other — the output can have more pieces than either input list, since one interval from firstList can intersect several intervals from secondList (see [24,25] in example 1, which overlaps two different secondList intervals).