Command Palette

Search for a command to run...

Hectal
Problem 15.7 · IntervalsMedium

Interval List Intersections

PatternTwo Pointers: Read and WriteMerge Intervals

What it teaches: Two sorted interval lists walked with two pointers: the intersection is [max of starts, min of ends], then advance the one that ends first.

Practise it on judges as “Interval List Intersections”.

The problem

Two lists of closed intervals are each sorted and pairwise disjoint. Return their intersection.

Example 1

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Constraints

  • 0 ≤ lengths ≤ 1000

Pattern clues in the wording

  • → Two sorted sequences processed together
  • → Overlap of a pair = [max start, min end]

These clues point to Two Pointers: Read and Write: A fast pointer reads every element and a slow pointer marks where the next kept element should be written.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        return new int[0][];
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
2
A = [[1,3],[5,9]]
B = []
[]

From slow to fast

Approaches

1. Optimal: two pointers · O(n + m)
1

Optimal: two pointers

Time O(n + m) Space O(n + m) for the output

lo = max(starts), hi = min(ends); if lo ≤ hi record [lo, hi]. Advance the pointer whose interval ends first.

Approach 1
import java.util.*;

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        List<int[]> out = new ArrayList<>();
        int i = 0, j = 0;
        while (i < A.length && j < B.length) {
            int lo = Math.max(A[i][0], B[j][0]);
            int hi = Math.min(A[i][1], B[j][1]);
            if (lo <= hi) out.add(new int[]{lo, hi});
            if (A[i][1] < B[j][1]) i++;
            else j++;
        }
        return out.toArray(new int[0][]);
    }
}

Verdict: Linear.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One list empty
  • Single-point intersections
  • One interval spanning many in the other list

Mistakes people make

  • Advancing both pointers after a match.

Interview

Follow-up questions

How would you compute the union of the two lists?