⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#986) before relying on it.

Interval List Intersections

An interactive visualization of the two-pointer approach to finding all intersections between two sorted interval lists. Watch how the algorithm compares intervals and advances pointers to collect every overlap.

Intervals LeetCode 986 ↗ Medium

The Problem

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [start_i, end_i] and secondList[j] = [start_j, end_j]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists. A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that is either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Interactive Visualization

First List (e.g. 0-2, 5-10)

Second List (e.g. 1-5, 8-12)

Preset

Speed:

Interval Timeline

A[i]

B[j]

Intersection

Intersections Found

No intersections yet

Code

fun intervalIntersection(firstList: Array<IntArray>, secondList: Array<IntArray>): List<IntArray> {    val result = mutableListOf<IntArray>()    var i = 0; var j = 0    while (i < firstList.size && j < secondList.size) {        val lo = maxOf(firstList[i][0], secondList[j][0])        val hi = minOf(firstList[i][1], secondList[j][1])        if (lo <= hi)            result.add(intArrayOf(lo, hi))        if (firstList[i][1] < secondList[j][1])            i++        else            j++    }    return result}

def intervalIntersection(firstList, secondList):    result = []    i, j = 0, 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:            result.append([lo, hi])        if firstList[i][1] < secondList[j][1]:            i += 1        else:            j += 1    return result

Current Step

Press Step or Play to begin.

How It Works

Key Insight

Since both interval lists are already sorted and pairwise disjoint, we can use two pointers to efficiently find all intersections in a single pass. At each step, we compare the current interval from each list. The intersection of two intervals [a1, a2] and [b1, b2] is [max(a1, b1), min(a2, b2)], and it exists only when max(a1, b1) <= min(a2, b2).

The Algorithm

Initialize two pointers i = 0 and j = 0 for the two lists, and an empty result list.
While both pointers are within bounds:
- Compute the potential intersection: lo = max(A[i][0], B[j][0]), hi = min(A[i][1], B[j][1]).
- If lo <= hi, this is a valid intersection — add [lo, hi] to the result.
- Advance the pointer whose current interval ends first: if A[i][1] < B[j][1], increment i; otherwise increment j.
Return the collected intersections.

Why Advance the One That Ends First?

The interval that ends first cannot possibly intersect with any later interval from the other list (since both lists are sorted). So we can safely move past it. The interval that ends later, however, might still overlap with the next interval from the other list, so we keep it.

Complexity

Time O(m + n)

Space O(m + n)

Each pointer moves forward at most m or n times respectively, where m and n are the lengths of the two lists. Each step does constant work. The output can contain at most m + n intervals in the worst case, so space is O(m + n) for the result.