Interval List Intersections (LC 986)

Pattern: Merge Intervals / Two Pointers
Difficulty: Medium
Key Concept: With two sorted, disjoint lists, walk both with two pointers; the intersection of current intervals is [max(starts), min(ends)] when max(starts) <= min(ends); advance the pointer whose interval ends first.

Problem Statement

You are given two lists of closed intervals firstList and secondList. Each list is sorted by start and intervals do not overlap within a list.

Return the intersection of the two lists: all intervals [x, y] that are exactly the overlap of some a from firstList and b from secondList, sorted and non-overlapping.

Input: firstList, secondList — int[][].
Output: int[][] — intersection intervals.

---

1. Algorithm & Pseudocode

Brute force

1. For each pair (i, j) with i in firstList, j in secondList, compute overlap.
2. Two intervals [a0,a1] and [b0,b1] overlap iff max(a0,b0) <= min(a1,b1); intersection is [max(a0,b0), min(a1,b1)].
3. Collect all non-empty intersections (and merge if needed—here they naturally stay ordered if you iterate in order).

Optimal (two pointers)

1. i = 0, j = 0, result empty list.
2. While i < firstList.length and j < secondList.length:
   • a = firstList[i], b = secondList[j].
   • lo = max(a[0], b[0]), hi = min(a[1], b[1]).
   • If lo <= hi, append [lo, hi] to result.
   • If a[1] < b[1], i++; else j++ (drop the interval that finishes first—it cannot intersect any later interval from the other list that still pairs with the longer one).
3. Return result.toArray(new int[0][]) (or equivalent).

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Why lo and hi? The overlap can only start at the later of the two starts (both must have begun) and end at the earlier of the two ends (first place one of them stops).
• Why skip when lo > hi? No overlap on this pair; we still must advance one pointer to make progress.
• Why advance the pointer with smaller end? That interval cannot meet any future interval on the other side that still overlaps the current longer interval in a new way without first moving past this shorter one—advancing the shorter end is safe and guarantees progress.
• Why not brute force? O(n × m) pairs; two pointers use O(n + m) because each pointer moves forward only.

---

3. The Dry Run

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

Step	i	j	a	b	lo = max(s)	hi = min(e)	lo <= hi?	Add to result	Advance
1	0	0	[0,2]	[1,5]	1	2	Yes	[1,2]	a[1]=2 < b[1]=5 → i++
2	1	0	[5,10]	[1,5]	5	5	Yes	[5,5]	b ends first (5 <= 10) → j++
3	1	1	[5,10]	[8,12]	8	10	Yes	[8,10]	a ends first → i++
4	2	1	[13,23]	[8,12]	13	12	No	—	b ends first → j++
5	2	2	[13,23]	[15,24]	15	23	Yes	[15,23]	a ends first → i++
6	3	2	[24,25]	[15,24]	24	24	Yes	[24,24]	b ends first → j++
7	3	3	[24,25]	[25,26]	25	25	Yes	[25,25]	a[1]=25 < b[1]=26 is false → j++
8	3	4	—	—	—	—	—	—	j == secondList.length → stop

Result list: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
(LeetCode 986 accepts these as valid interval intersections.)

---

4. Java Solution

Brute Force

import java.util.*;

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> out = new ArrayList<>();
        for (int[] a : firstList) {
            for (int[] b : secondList) {
                int lo = Math.max(a[0], b[0]);
                int hi = Math.min(a[1], b[1]);
                if (lo <= hi) {
                    out.add(new int[] { lo, hi });
                }
            }
        }
        return out.toArray(new int[0][]);
    }
}

Time: O(n × m). Space: O(1) excluding output list.

Optimal

import java.util.*;

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

Time: O(n + m). Space: O(1) excluding output; O(k) for k intersections.

---

5. The “Java vs. Others” Edge

• Math.max / Math.min for int are clear and avoid manual branching for intersection bounds.
• ArrayList<int[]> + toArray(new int[0][]): You don’t need to know the number of intersections upfront; grow the list and convert at the end. List<int[]> is often cleaner than repeatedly resizing a raw int[][] in Java.
• C++: Typically vector<vector<int>> ans and push_back({lo, hi}); you manage capacity less explicitly than Java’s ArrayList growth.
• Python: list.append then return; Java’s typing is more verbose but the two-pointer logic is identical.
• Tie on a[1] == b[1]: Using if (a[1] < b[1]) i++; else j++; advances j when ends are equal—either pointer works for correctness; pick one rule and stay consistent.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n × m)	O(k) output	Every pair; k = number of intersection pieces.
Optimal	O(n + m)	O(k) output	Two pointers; each index increases monotonically.