Interval List Intersections

Problem

Given two lists of closed intervals already sorted by start (and pairwise disjoint inside each list), return their intersection as a list of intervals.

Constraints

• 0 ≤ A.length, B.length ≤ 1000

Approach — Two Pointers

This is a Two Pointers problem. The idea: walk two indices through the data together (or toward each other), turning an O(n²) pair search into one linear pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(1) extra space.

Solution code

Python

class Solution:
    def intervalIntersection(self, A, B):
        res = []
        i = j = 0
        while i < len(A) and j < len(B):
            lo = max(A[i][0], B[j][0])
            hi = min(A[i][1], B[j][1])
            if lo <= hi:
                res.append([lo, hi])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
        return res

Java

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][]);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.