Interval List Intersections

Medium Intervals Basics Original on LeetCode

Reported atDoorDash

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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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.
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++.
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.