MediumArrayTwo PointersSweep LineUpdated Sep 2026

986. Interval List Intersections

Asked at Meta

Difficulty

Medium

Time

O(m + n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You get two lists of closed intervals, firstList and secondList. Each interval is written as [start, end] and covers every number from start to end, including both ends. Inside each list the intervals do not overlap each other, and they are sorted by start.

Return a list of all the intervals that belong to both lists — that is, every range of numbers covered by some interval in firstList and also by some interval in secondList. The answer must be sorted by start, and the returned intervals must not overlap each other.

Two intervals [a1, a2] and [b1, b2] overlap when the later start is not bigger than the earlier end. Their shared part is [max(a1, b1), min(a2, b2)]. If that range is empty, the two intervals do not intersect. Note that a single point counts: [1, 5] and [5, 8] share [5, 5].

Where do the two lists overlap?

firstList[0,2][5,10][13,23][24,25]0123The first list, sorted and non-overlapping.secondList[1,5][8,12][15,24][25,26]0123The second list, also sorted and non-overlapping.answer[1,2][5,5][8,10][15,23][24,24][25,25]012345The orange entries are single points — the two intervals only touchat one number.
Every place where a bar from the top list and a bar from the bottom list cover the same numbers becomes one interval in the answer.

Constraints

  • ●0 <= firstList.length, secondList.length <= 1000
  • ●firstList.length + secondList.length >= 1
  • ●0 <= starti < endi <= 10^9
  • ●0 <= startj < endj <= 10^9
  • ●Each list is sorted by start and has no overlapping intervals inside it

Examples

Example 1
InputfirstList = [[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]]
Why[0,2] meets [1,5] on [1,2]. [5,10] touches [1,5] at the single point 5, then meets [8,12] on [8,10]. [13,23] meets [15,24] on [15,23]. [24,25] meets [15,24] at 24 and [25,26] at 25.
Example 2
InputfirstList = [[1,3],[5,9]], secondList = []
Output[]
WhyThe second list has no intervals, so nothing can be shared. The answer is empty.

Asked At

1 companies
CompanyDifficulty
MetaMediumView all Meta questions →

How to Think About It

1

Brute force: For each interval in list A, compare against every interval in list B for overlap.

2

Two pointers: Walk through both lists simultaneously, advancing the pointer of the interval with the smaller end.

3

Intersection of two intervals [a1, a2] and [b1, b2] is [max(a1,b1), min(a2,b2)] if max start <= min end.

4

Advance the pointer whose interval ends first since it cannot intersect with any later interval in the other list.

5

Two pointers approach achieves O(m + n) time and O(1) extra space.

Optimal Approach

Use two pointers i and j on the two interval lists. For each pair, compute the intersection as [max(start_i, start_j), min(end_i, end_j)]. If this is valid (start <= end), add it to the result. Then advance whichever pointer corresponds to the interval with the smaller end value, because that interval cannot overlap with any future interval in the other list.

Two pointers, advance the one that ends first

firstList[0,2][5,10][13,23][24,25]0123iStart with i = 0 and j = 0.secondList[1,5][8,12][15,24][25,26]0123jCompare [0,2] with [1,5]: overlap is [max(0,1),min(2,5)] = [1,2].lo = max(start_i, start_j)hi = min(end_i, end_j)if lo <= hi: save [lo, hi]move the pointer with the smaller endi=0, j=0 → save [1,2], end 2 < 5, i++i=1, j=0 → save [5,5], end 5 = 5, j++i=1, j=1 → save [8,10], end 10 < 12, i++i=2, j=1 → no overlap, end 12 < 23, j++i=2, j=2 → save [15,23], then [24,24] and [2Each step either records an overlap or skips aninterval that can no longer match anything ahead.
Compare the current pair, save the overlap, then move the pointer whose interval finishes earlier.
ComplexityTime O(m + n)Space O(1)Each step moves one pointer forward, so the total work is the sum of both list lengths; only the output list uses extra memory.

What Trips People Up in Real Interviews

1

Confirm both input lists are already sorted by start time.

2

Clarify that intersections are inclusive: [1,3] and [3,5] intersect at [3,3].

3

Explain why we advance the pointer with the smaller end value.

4

Edge cases: no intersections at all, one list empty, intervals touching at a single point.

5

Discuss that the output size is bounded by m + n.

Solution Code

O(m + n) time
def intervalIntersection(firstList, secondList):
    result = []
    i = j = 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

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Interval List Intersections problem?

Given two lists of closed intervals sorted by start, find all their intersections. Each interval is [start, end] with start <= end. Return the list of intersection intervals.

How do you solve Interval List Intersections?

The optimal approach runs in O(m + n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Interval List Intersections?

Interval List Intersections is asked at Meta. It is a medium difficulty problem.

What are common mistakes on Interval List Intersections?
  • Confirm both input lists are already sorted by start time.
  • Clarify that intersections are inclusive: [1,3] and [3,5] intersect at [3,3].
  • Explain why we advance the pointer with the smaller end value.
  • Edge cases: no intersections at all, one list empty, intervals touching at a single point.
  • Discuss that the output size is bounded by m + n.