304. Interval List Intersections

🔗 LeetCode Problem: 986. Interval List Intersections
📊 Difficulty: Medium
🏷️ Topics: Array, Two Pointers

Problem Statement

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

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

Constraints: - 0 <= firstList.length, secondList.length <= 1000 - firstList.length + secondList.length >= 1 - 0 <= starti < endi <= 10^9 - endi < starti+1 - 0 <= startj < endj <= 10^9 - endj < startj+1

---

🌳 Visual Understanding - The Intersection Problem

The Problem We're Solving:

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

Timeline visualization:

First:   [0, 2]     [5,     10]       [13,          23] [24,25]
         |---|      |-------|         |---------------|  |-|
Second:      [1,  5]    [8,      12]     [15,         24]  [25,  26]
             |-----|    |---------|      |-------------|   |-----|

Intersections:
  [0,2] ∩ [1,5] = [1,2] ✓
  [5,10] ∩ [1,5] = [5,5] ✓ (single point!)
  [5,10] ∩ [8,12] = [8,10] ✓
  [13,23] ∩ [15,24] = [15,23] ✓
  [24,25] ∩ [15,24] = [24,24] ✓ (single point!)
  [24,25] ∩ [25,26] = [25,25] ✓ (single point!)

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

Understanding Intersection:

Two intervals [a,b] and [c,d] intersect if they have common points

Intersection exists if:
  a <= d AND c <= b
  (First starts before second ends AND second starts before first ends)

When they intersect, intersection is:
  [max(a,c), min(b,d)]

Examples:
  [1,3] ∩ [2,4] = [max(1,2), min(3,4)] = [2,3] ✓
  [1,5] ∩ [3,7] = [max(1,3), min(5,7)] = [3,5] ✓
  [1,3] ∩ [5,7] = No intersection (3 < 5)

Key Observations:

1. Both lists are SORTED and DISJOINT
   Within each list, no overlaps!
   firstList[i].end < firstList[i+1].start

2. Need to find ALL intersections
   Not just count, but actual intervals

3. Can use TWO POINTERS!
   Since both sorted, process chronologically

4. After checking intersection:
   Advance pointer for interval that ends earlier
   (The one ending later might intersect with next!)

---

🧠 The AHA Moment - Two Pointers Strategy

Approach 1: Brute Force (For Understanding)

For each interval in firstList:
  For each interval in secondList:
    Check if they intersect
    If yes, add intersection

Time: O(m × n)
Works but inefficient! 🤔

Approach 2: Two Pointers (Optimal!)

Key insight: Both lists are SORTED!

Use two pointers:
  i for firstList
  j for secondList

At each step:
  1. Check if firstList[i] and secondList[j] intersect
  2. If yes, add intersection to result
  3. Move pointer for interval that ends earlier
     (Other interval might intersect with next!)

Time: O(m + n) - Linear!
OPTIMAL! 🎯

Visual Discovery:

firstList:  [[0,2], [5,10]]
secondList: [[1,5], [8,12]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 1: i=0, j=0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

firstList[0] = [0,2]
secondList[0] = [1,5]

Check intersection:
  0 <= 5? YES
  1 <= 2? YES
  They intersect!

Intersection: [max(0,1), min(2,5)] = [1,2] ✓

Which ends earlier?
  2 < 5 → first[0] ends earlier
  Move i++

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 2: i=1, j=0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

firstList[1] = [5,10]
secondList[0] = [1,5]

Check intersection:
  5 <= 5? YES
  1 <= 10? YES
  They intersect!

Intersection: [max(5,1), min(10,5)] = [5,5] ✓ (single point!)

Which ends earlier?
  10 < 5? NO, 5 < 10
  second[0] ends earlier (or equal)
  Move j++

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 3: i=1, j=1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

firstList[1] = [5,10]
secondList[1] = [8,12]

Check intersection:
  5 <= 12? YES
  8 <= 10? YES
  They intersect!

Intersection: [max(5,8), min(10,12)] = [8,10] ✓

Which ends earlier?
  10 < 12 → first[1] ends earlier
  Move i++

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 4: i=2, j=1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

i >= firstList.length
Stop!

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: [[1,2], [5,5], [8,10]]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

---

🟢 Approach: Two Pointers (Optimal)

🎨 Building the Complete Solution

Step 1: Initialize Two Pointers

i = 0 (pointer for firstList)
j = 0 (pointer for secondList)
result = []

Step 2: Process While Both Valid

While i < firstList.length AND j < secondList.length:

  Get intervals:
    first = firstList[i]
    second = secondList[j]

  Check intersection:
    If first.start <= second.end AND second.start <= first.end:
      // They intersect!
      intersection = [max(first.start, second.start), 
                     min(first.end, second.end)]
      Add intersection to result

  Move pointer:
    If first.end < second.end:
      i++ (first ends earlier)
    Else:
      j++ (second ends earlier or same)

Step 3: Return Result

Return all intersections found

📝 Implementation - Clean and Clear

import java.util.*;

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> result = new ArrayList<>();
        int i = 0, j = 0;

        while (i < firstList.length && j < secondList.length) {
            // Get current intervals
            int[] first = firstList[i];
            int[] second = secondList[j];

            // Check if they intersect
            // Condition: first.start <= second.end AND second.start <= first.end
            if (first[0] <= second[1] && second[0] <= first[1]) {
                // They intersect! Find intersection
                int start = Math.max(first[0], second[0]);
                int end = Math.min(first[1], second[1]);
                result.add(new int[]{start, end});
            }

            // Move pointer for interval that ends earlier
            if (first[1] < second[1]) {
                i++;
            } else {
                j++;
            }
        }

        return result.toArray(new int[result.size()][]);
    }
}

🔍 Complete Dry Run - Example 1

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

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

i = 0, j = 0
result = []

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 1: i=0, j=0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

first = [0,2], second = [1,5]

Check intersection:
  0 <= 5? YES
  1 <= 2? YES
  → Intersect!

Intersection: [max(0,1), min(2,5)] = [1,2]
result = [[1,2]]

Which ends earlier?
  2 < 5 → i++ → i=1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 2: i=1, j=0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

first = [5,10], second = [1,5]

Check intersection:
  5 <= 5? YES
  1 <= 10? YES
  → Intersect!

Intersection: [max(5,1), min(10,5)] = [5,5]
result = [[1,2], [5,5]]

Which ends earlier?
  10 < 5? NO → j++ → j=1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 3: i=1, j=1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

first = [5,10], second = [8,12]

Check intersection:
  5 <= 12? YES
  8 <= 10? YES
  → Intersect!

Intersection: [max(5,8), min(10,12)] = [8,10]
result = [[1,2], [5,5], [8,10]]

Which ends earlier?
  10 < 12 → i++ → i=2

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 4: i=2, j=1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

first = [13,23], second = [8,12]

Check intersection:
  13 <= 12? NO
  → No intersection!

Which ends earlier?
  23 < 12? NO → j++ → j=2

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 5: i=2, j=2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

first = [13,23], second = [15,24]

Check intersection:
  13 <= 24? YES
  15 <= 23? YES
  → Intersect!

Intersection: [max(13,15), min(23,24)] = [15,23]
result = [[1,2], [5,5], [8,10], [15,23]]

Which ends earlier?
  23 < 24 → i++ → i=3

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 6: i=3, j=2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

first = [24,25], second = [15,24]

Check intersection:
  24 <= 24? YES
  15 <= 25? YES
  → Intersect!

Intersection: [max(24,15), min(25,24)] = [24,24]
result = [[1,2], [5,5], [8,10], [15,23], [24,24]]

Which ends earlier?
  25 < 24? NO → j++ → j=3

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 7: i=3, j=3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

first = [24,25], second = [25,26]

Check intersection:
  24 <= 26? YES
  25 <= 25? YES
  → Intersect!

Intersection: [max(24,25), min(25,26)] = [25,25]
result = [[1,2], [5,5], [8,10], [15,23], [24,24], [25,25]]

Which ends earlier?
  25 < 26 → i++ → i=4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Loop ends: i=4 >= firstList.length
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

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

Complete Dry Run - Example 2 (Edge Case)

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

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

i = 0, j = 0
secondList.length = 0

Loop condition: i < 2 AND j < 0?
  0 < 2 (YES) AND 0 < 0 (NO)
  → Condition FALSE

Loop never executes!

Return: [] ✓

📊 Complexity Analysis

Time Complexity: O(m + n)

m = length of firstList
n = length of secondList

Each pointer moves forward only
Each interval visited at most once
Total: O(m + n)

LINEAR! Optimal! 🎯

Space Complexity: O(1) or O(k)

O(1) excluding output space
Output space: O(k) where k = number of intersections
  In worst case: k = min(m, n)

---

🎯 Key Insights Summary

The Three Critical Points:

1. Two Pointers on Sorted Lists

Both lists sorted → use two pointers!

Process chronologically:
  Compare current intervals from both lists
  Find intersection if exists
  Move pointer strategically

This is the KEY pattern! 🔑

2. Intersection Formula

Two intervals [a,b] and [c,d] intersect if:
  a <= d AND c <= b

When they intersect:
  intersection = [max(a,c), min(b,d)]

This formula is CRITICAL to remember! ✓

3. Which Pointer to Move

After checking intersection:
  Move pointer for interval that ENDS EARLIER

Why?
  The interval ending later might still intersect
  with the NEXT interval from the other list!

This ensures we don't miss any intersections! 🎯

---

💡 Why This Approach Works - Deep Intuition

The Sorting Property:

Key property: Both lists are SORTED

This means:
  If firstList[i] doesn't intersect with secondList[j],
  and firstList[i] ends before secondList[j],
  then firstList[i] won't intersect with secondList[j+1], j+2, ...
  (because they all start even later!)

Therefore: Safe to move to next interval! ✓

Why Move the Earlier-Ending Interval:

Scenario: first = [5,10], second = [8,15]

If we move second (ending later):
  We might miss intersection of [5,10] with next from second!

If we move first (ending earlier):
  [5,10] already covered all possible intersections
  (Any future second intervals start after 10)
  Safe to move! ✓

Always move the earlier-ending interval! 🎯

---

⚠️ Common Mistakes

// Mistake 1: Wrong intersection condition
if (first[0] < second[1] && second[0] < first[1]) { // ❌ Should be <=
// ✓ CORRECT: Use <= to handle touching intervals
if (first[0] <= second[1] && second[0] <= first[1]) {

// Mistake 2: Wrong intersection calculation
int start = Math.min(first[0], second[0]); // ❌ Should be max!
int end = Math.max(first[1], second[1]);   // ❌ Should be min!
// ✓ CORRECT:
int start = Math.max(first[0], second[0]);
int end = Math.min(first[1], second[1]);

// Mistake 3: Wrong pointer advancement
if (first[1] <= second[1]) { // ❌ Both might advance when equal!
// ✓ CORRECT: Use < for tie-breaking
if (first[1] < second[1]) {
    i++;
} else {
    j++;
}

// Mistake 4: Not handling empty lists
// ❌ No edge case check needed!
// Loop naturally handles empty lists (condition fails immediately)
// This is actually GOOD - no special case needed!

// Mistake 5: Trying to handle non-intersecting separately
if (!intersect) {
    // Some complex logic ❌
}
// ✓ CORRECT: Just move pointer, no need for special case!
// The pointer movement handles it naturally

---

📝 Quick Revision Notes

🎯 Core Concept

Problem: Find all intersections between two sorted interval lists

Key Insight: Two pointers on sorted lists!

Algorithm: 1. Use two pointers (i, j) 2. Check if current intervals intersect 3. If yes: add [max(starts), min(ends)] 4. Move pointer for earlier-ending interval

Why It Works: Sorted lists + greedy pointer movement ensures all intersections found!

⚡ Quick Implementation

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
  public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
    return twoPointers(firstList, secondList);
  }

  private int[][] twoPointers(int[][] firstList, int[][] secondList) {
    List<int[]> list = new ArrayList<>();

    // step 1: initialize pointers
    int i = 0;
    int j = 0;

    while (i < firstList.length && j < secondList.length) {
      int[] first = firstList[i];
      int[] second = secondList[j];

      // step 2: decide intersection point
      // if first(a, b) and second(c, d) overlap, then a <= d and c <= b
      // (0, 2) and (1, 5) => 0 <= 5 and 1 <= 2
      // intersection: (max(0, 1), min(2, 5))
      if (first[0] <= second[1] && second[0] <= first[1]) {
        list.add(new int[] { Math.max(first[0], second[0]), Math.min(first[1], second[1]) });
      }

      // step 3: proceed to next step or check
      // first list => (0,2),(5,10) and
      // second list => (1,5),(8,12)
      // We are done with i = 0 which is (0,2) and j = 0 which is (1,5)
      // Now what to move, i or j?
      if (first[1] < second[1]) {
        // case 1: why i++?
        // firstt: [------]
        // second: [----------]
        // first ends earlier. Even if second overlaps first now, first is done after
        // this point. No future interval in secondList can overlap this first
        // interval, because future second intervals start even later. So, move i.
        i++;
      } else {
        // case 2: why j++?
        // firstt: [----------]
        // second: [------]
        // second ends earlier.
        // Same logic: second cannot overlap anything else in firstList. So, move j.
        j++;
      }
    }

    return list.toArray(new int[list.size()][]);
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    // [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
    System.out
        .println(Arrays.deepToString(s.intervalIntersection(new int[][] { { 0, 2 }, { 5, 10 }, { 13, 23 }, { 24, 25 } },
            new int[][] { { 1, 5 }, { 8, 12 }, { 15, 24 }, { 25, 26 } })));

    // []
    System.out.println(Arrays.deepToString(s.intervalIntersection(new int[][] { { 1, 3 }, { 5, 9 } }, new int[][] {})));
  }
}

🔑 Key Points

✓ Two pointers on sorted lists
✓ Intersection check: a<=d AND c<=b
✓ Intersection: [max(starts), min(ends)]
✓ Move earlier-ending interval pointer
✓ Use < not <= for pointer advancement
✓ Time: O(m+n), Space: O(1)
✓ No special handling for empty lists needed

🎪 Memory Aid

"Two pointers march in line!"
"Max of starts, min of ends define!"
"Earlier ending, forward we incline!"
"Sorted lists make intersections shine!" ✨

---

🎉 Congratulations!

You've mastered Interval List Intersections!

What You Learned:

✅ Two pointers on sorted lists - Classic pattern
✅ Intersection formula - Max of starts, min of ends
✅ Strategic pointer movement - Earlier-ending advances
✅ Linear time solution - O(m+n) optimal
✅ Clean boundary handling - No special cases needed

The Beautiful Insight:

Sorted Lists → Two Pointers → Linear Solution

The core insight:
  "Both lists sorted → process chronologically"
  "Compare current from each, find intersection"
  "Move strategically to avoid missing any"

  Intersection formula:
    Check: a <= d AND c <= b
    Result: [max(a,c), min(b,d)]

  Pointer strategy:
    Move the earlier-ending one
    (Later-ending might intersect with next!)

  This gives LINEAR time - optimal!

This two-pointer pattern appears everywhere:
  - Merge sorted lists
  - Find common elements
  - Range intersections
  - Any sorted data comparison

Master this = Recognize merge opportunities! ✨

Interview Mastery:

When asked about Interval List Intersections:

1. Understand: "Find all intersections between two sorted lists"

2. Clarify: "Both lists are sorted and disjoint, right?"

3. Key insight: "Both sorted → use two pointers!"

4. Intersection check: "Intervals [a,b] and [c,d] intersect if
   a <= d AND c <= b. Simple cross-check!"

5. Intersection formula: "When they intersect:
   [max(a,c), min(b,d)]
   Max of starts, min of ends!"

6. Pointer movement: "Move pointer for earlier-ending interval.
   Why? Later-ending might intersect with next from other list!"

7. Code it: Clean O(m+n) solution

8. Complexity: "O(m+n) time - visit each interval once.
   O(1) space excluding output."

9. Edge cases: "Empty lists handled naturally by loop condition!"

Shows complete understanding! 💯

You've mastered a beautiful two-pointer interval problem! This pattern of merging/comparing sorted lists is fundamental! 🚀✨🎯