Interval List Intersections: Two-Pointer Merge

LeetCode 986, Interval List Intersections, gives you two sorted lists of closed, disjoint intervals and asks you to find every region where they overlap. It is a natural extension of the merge-intervals family, but instead of combining intervals you are extracting the places where two sets of ranges agree.

The problem

You are given two lists of closed intervals, firstList and secondList. Each list is sorted by start time, and within each list the intervals are pairwise disjoint (no overlaps). 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.

Example: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] produces [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].

Each pair of overlapping intervals from A and B produces one intersection. Notice that some intersections are single points, like [5,5], where the intervals touch at exactly one value.

Why this problem matters

Interval intersection is a fundamental operation in scheduling, computational geometry, and database query planning. If you have two calendars and want to find mutual free time, or two sets of ranges and need the overlap, this is the pattern you reach for. It also reinforces the two-pointer technique on sorted data, which carries over to dozens of other problems.

The brute force approach

You could compare every interval in A against every interval in B, checking for overlap each time:

def intervalIntersection(firstList, secondList):
    result = []
    for a in firstList:
        for b in secondList:
            lo = max(a[0], b[0])
            hi = min(a[1], b[1])
            if lo <= hi:
                result.append([lo, hi])
    return result

This works but runs in O(m * n) time, where m and n are the lengths of the two lists. Since both lists are already sorted, you can do much better.

The key insight

Because both lists are sorted and disjoint, you can walk through them simultaneously with two pointers. At each step you check whether the current pair of intervals overlaps. If they do, you record the intersection. Then you advance the pointer whose interval ends first, because that interval cannot overlap with anything further in the other list.

The intersection of two intervals [a0, a1] and [b0, b1] exists when max(a0, b0) <= min(a1, b1). The overlap region is [max(a0, b0), min(a1, b1)].

The pointer-advance rule is clean: whichever interval ends earlier gets discarded, because the interval that ends later might still overlap with the next interval in the other list.

Walking through it step by step

Let's trace through firstList = [[0,2],[5,10],[13,23],[24,25]] and secondList = [[1,5],[8,12],[15,24],[25,26]].

Every step follows the same logic. Compute the overlap. If it exists, add it to the result. Advance the pointer for whichever interval ends sooner. When either pointer runs past the end of its list, you are done.

The two-pointer solution

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

That is the entire solution. Two pointers, one overlap check, one advance rule. No sorting needed because the input is already sorted.

Complexity analysis

Time: O(m + n). Each pointer advances at most m or n times respectively. Every step does O(1) work.

Space: O(m + n). The result list can contain at most m + n intersections (though typically fewer). If you exclude the output, the auxiliary space is O(1).

Building blocks

Interval List Intersections combines two reusable patterns.

Two-pointer merge on sorted sequences

When you have two sorted sequences and need to process them together, the two-pointer technique lets you walk through both in a single linear pass. The general skeleton:

def two_pointer_merge(A, B):
    result = []
    i, j = 0, 0
    while i < len(A) and j < len(B):
        # process A[i] and B[j]
        # advance the pointer that should move
        pass
    return result

This same structure powers merge sort's merge step, finding the intersection of two sorted arrays, and merging two sorted linked lists.

Interval overlap detection

Two intervals [a0, a1] and [b0, b1] overlap when max(a0, b0) <= min(a1, b1). The overlap region is [max(a0, b0), min(a1, b1)]. This formula appears in almost every interval problem:

def overlap(a, b):
    lo = max(a[0], b[0])
    hi = min(a[1], b[1])
    if lo <= hi:
        return [lo, hi]
    return None

Knowing this overlap formula by heart saves you from drawing cases on paper every time. It handles all configurations: partial overlap, containment, touching at a point, and no overlap.

Edge cases

One list is empty. If either list has no intervals, the result is empty. The while loop condition handles this naturally.

No overlaps at all. If the two lists cover completely separate ranges (like A = [[1,3]] and B = [[5,7]]), the overlap check always fails. The pointers still advance correctly, and the result stays empty.

Single-point intersections. When one interval ends exactly where another begins (like [0,2] and [2,5]), the overlap is [2,2]. This is a valid closed interval containing just one point. The lo <= hi check captures it.

One interval fully contains another. If [5,10] overlaps [6,8], the intersection is [6,8]. The max/min formula handles containment without any special logic.

Lists of different lengths. The algorithm does not require the two lists to have the same number of intervals. The loop stops as soon as either pointer reaches the end.

Common mistakes

Using the wrong advance rule. If you always advance i, or always advance the pointer with the smaller start, you will miss intersections. The correct rule is to advance whichever pointer's interval has the smaller end value, because that interval is done contributing.

Off-by-one on the overlap check. Using strict less-than (lo < hi) instead of less-than-or-equal (lo <= hi) misses single-point intersections like [5,5]. The problem says closed intervals, so endpoints count.

Forgetting to advance when there is no overlap. When two intervals do not overlap, you still need to advance a pointer. The same "smaller end" rule applies whether or not an intersection was found.

From understanding to recall

The two-pointer intersection pattern is short, but the details trip people up in interviews. Which value do you take max of? Which do you take min of? How do you decide which pointer to advance? These are the kinds of small decisions that feel obvious when reading the solution but become easy to mix up under pressure.

The way to lock this in is to practice writing the solution from scratch until the overlap formula and the advance rule feel automatic. Start with the two-pointer skeleton, fill in the overlap check, add the advance logic, and test on an example. Once you can do that without looking at the code, you own the pattern.

CodeBricks breaks problems like this into building blocks and drills them with spaced repetition. Instead of re-reading the solution before every interview, you practice recalling the pieces that matter until they stick.

Related posts

• Merge Intervals - The foundational interval pattern: sort and sweep to merge overlapping ranges
• Insert Interval - Insert a new interval into a sorted list, merging overlaps in a single pass
• Meeting Rooms II - Count maximum simultaneous overlaps using sorted intervals and a heap

---

Visual Learner? See how sorting algorithms work with our Sorting Visualizations.