LeetCode Problem 986: Interval List Intersections

1. Problem Overview

This problem deals with two lists of intervals. Each list contains non-overlapping intervals, and the intervals in each list are sorted in ascending order by their start time.

The task is to find all intersections between the two lists of intervals — that is, all intervals that overlap between the two lists.

Problem Statement (LeetCode 986)

You are given two lists of closed intervals, firstList and secondList.
Each interval is a pair of integers [start, end], where start <= end.
Return the list of intervals where the two lists overlap.

Example 1:

Input:
firstList  = [[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]]

Example 2:

Input:
firstList  = [[1,3],[5,9]]
secondList = []
Output:
[]

Example 3:

Input:
firstList  = []
secondList = [[4,8],[10,12]]
Output:
[]

2. Understanding the Problem

Let’s analyze what an interval intersection means.

Two intervals:

A = [a1, a2]
B = [b1, b2]

These two intervals overlap if and only if:

a1 <= b2 AND b1 <= a2

When they overlap, their intersection interval is:

[max(a1, b1), min(a2, b2)]

This gives the overlapping segment between the two.

3. Example Visualization

Let’s take the first example:

firstList  = [ [0,2], [5,10], [13,23], [24,25] ]
secondList = [ [1,5], [8,12], [15,24], [25,26] ]

We can visualize it on a timeline:

firstList : 0----2     5----------10     13-------------23  24--25
secondList:   1-----5       8----12        15-----------24    25---26

Now we compare:

[0,2] and [1,5] → overlap: [1,2]
[5,10] and [1,5] → overlap: [5,5]
[5,10] and [8,12] → overlap: [8,10]
[13,23] and [15,24] → overlap: [15,23]
[24,25] and [15,24] → overlap: [24,24]
[24,25] and [25,26] → overlap: [25,25]

Thus, output = [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

4. Step-by-Step Approach

We’ll use a two-pointer technique, because both interval lists are already sorted by their start times.

Algorithm

Initialize two pointers i and j to 0.
While both pointers are within their lists:
- Let A = firstList[i] and B = secondList[j].
- Find the intersection between A and B:
  - start = max(A[0], B[0])
  - end = min(A[1], B[1])
- If start <= end, add [start, end] to the result.
- Move the pointer that has the smaller end time forward:
  - If A[1] < B[1], increment i.
  - Else, increment j.
Repeat until one list is fully processed.

5. Java Implementation

import java.util.*;

public class IntervalListIntersections {

    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> result = new ArrayList<>();

        int i = 0, j = 0;

        // Traverse both lists
        while (i < firstList.length && j < secondList.length) {
            int startA = firstList[i][0];
            int endA = firstList[i][1];
            int startB = secondList[j][0];
            int endB = secondList[j][1];

            // Check if intervals overlap
            int start = Math.max(startA, startB);
            int end = Math.min(endA, endB);

            // If valid intersection
            if (start <= end) {
                result.add(new int[]{start, end});
            }

            // Move the pointer with the smaller endpoint
            if (endA < endB) {
                i++;
            } else {
                j++;
            }
        }

        // Convert list to array
        return result.toArray(new int[result.size()][]);
    }

    public static void main(String[] args) {
        IntervalListIntersections obj = new IntervalListIntersections();

        int[][] firstList = {{0,2},{5,10},{13,23},{24,25}};
        int[][] secondList = {{1,5},{8,12},{15,24},{25,26}};

        int[][] output = obj.intervalIntersection(firstList, secondList);

        System.out.println("Intersections:");
        for (int[] interval : output) {
            System.out.println(Arrays.toString(interval));
        }
    }
}

6. Example Walkthrough

Let’s walk through the same example step by step:

firstList  = [ [0,2], [5,10], [13,23], [24,25] ]
secondList = [ [1,5], [8,12], [15,24], [25,26] ]

Iteration 1:

A = [0,2], B = [1,5]
start = max(0,1) = 1
end = min(2,5) = 2
→ Overlap: [1,2]
Move A forward (since 2 < 5)

Iteration 2:

A = [5,10], B = [1,5]
start = max(5,1) = 5
end = min(10,5) = 5
→ Overlap: [5,5]
Move B forward (since 10 > 5)

Iteration 3:

A = [5,10], B = [8,12]
start = 8, end = 10
→ Overlap: [8,10]
Move A forward (10 < 12)

Iteration 4:

A = [13,23], B = [8,12]
No overlap (13 > 12)
Move B forward

Iteration 5:

A = [13,23], B = [15,24]
start = 15, end = 23
→ Overlap: [15,23]
Move A forward (23 < 24)

Iteration 6:

A = [24,25], B = [15,24]
start = 24, end = 24
→ Overlap: [24,24]
Move A forward (25 > 24 → move B forward)

Iteration 7:

A = [24,25], B = [25,26]
start = 25, end = 25
→ Overlap: [25,25]
Move both forward → done

Result: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

7. Complexity Analysis

Time Complexity: O(M + N)
- We traverse both lists once, where M and N are lengths of the two lists.
Space Complexity: O(K)
- For storing K intersection intervals in the result list.

8. Edge Cases

One or both lists empty → return empty array.
No overlapping intervals → return empty array.
Identical intervals → the entire interval is included.
Intervals touching at endpoints (like [1,2] and [2,3]) → intersection is [2,2].

9. Key Takeaways

Use two pointers when dealing with sorted interval lists.
The intersection condition is start <= end.
Always advance the pointer with the smaller end time, since that interval can no longer intersect with any future intervals from the other list.
This approach avoids extra space and unnecessary comparisons.