Start practising

Interval List Intersections

Medium Intervals Basics Original on LeetCode

Interval List Intersections is a medium intervals problem solved with the basics pattern. The best approach, optimal (two pointers), runs in O(m + n) time and O(1) space. Below are 2 approaches in Java, from compare every pair up.

Problem

You get two lists of closed intervals, each sorted and non-overlapping. Return every intersection between an interval of the first list and one of the second.

Examples

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]]

Example 2

Input
A = [[1,3]], B = []
Output
[]

Constraints

  • Each list is sorted and pairwise disjoint; closed intervals.
  • Up to 1000 intervals per list.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Compare every pairO(m · n)O(1)
Optimal (two pointers)O(m + n)O(1)

1Compare every pair

TimeO(m · n)
SpaceO(1)

Check every interval of A against every interval of B and keep the non-empty intersections, then sort.

  1. lo = max(starts), hi = min(ends); if lo <= hi, record.
Java
class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        List<int[]> out = new ArrayList<>();
        for (int[] a : A)
            for (int[] b : B) {
                int lo = Math.max(a[0], b[0]), hi = Math.min(a[1], b[1]);
                if (lo <= hi) out.add(new int[] { lo, hi });
            }
        out.sort((x, y) -> Integer.compare(x[0], y[0]));
        return out.toArray(new int[0][]);
    }
}

2Optimal (two pointers)

TimeO(m + n)
SpaceO(1)

Both lists are sorted. For the current pair, the intersection is [max start, min end] if non-empty. The interval that ends first cannot meet anything else in the other list, so advance it.

  1. i = j = 0.
  2. lo = max(A[i][0], B[j][0]); hi = min(A[i][1], B[j][1]); if lo <= hi add.
  3. If A[i][1] < B[j][1], i++; else j++.
Java
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]), 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][]);
    }
}

Edge cases to test

  • Intersections that are single points
  • One list empty

Hints

Hint 1

Compare the current intervals of both lists, record their intersection if any, then advance whichever one ends first.

FAQ

What is the best time complexity for Interval List Intersections?

Optimal (two pointers) runs in O(m + n) time and O(1) extra space.

Which pattern does Interval List Intersections use?

It is a intervals problem that uses the basics pattern. Other problems with the same pattern: Detect overlap unsorted, Detect overlap sorted intervals, Meeting Rooms.

Is there a brute force solution for Interval List Intersections?

Yes. Compare every pair takes O(m · n) time and O(1) space. Check every interval of A against every interval of B and keep the non-empty intersections, then sort.

Which edge cases should I test for Interval List Intersections?

Intersections that are single points; One list empty.