The O(n) Club: Surviving Interval List Intersections Without Meltdowns

The O(n) Club: Surviving Interval List Intersections Without Meltdowns

⚡ TL;DR

Need to intersect two sorted, non-overlapping interval lists in real life (or at least in Java)? Two pointers. Minimal drama. Here’s the quick-and-dirty:

// L and R = int[][] arrays of [start, end]
int i = 0, j = 0;
while (i < L.length && j < R.length) {
    int lo = Math.max(L[i][0], R[j][0]);
    int hi = Math.min(L[i][1], R[j][1]);
    if (lo <= hi) add lo-hi interval to result;
    if (L[i][1] < R[j][1]) i++; else j++;
}

🧠 How Devs Usually Mess This Up

Oh, the nostalgia of nested loops: for every interval in A, check every interval in B, and pretend your processor is powered by a small nuclear reactor. Also classic: panicking and trying to merge or sort the lists, even though the prompt says “sorted” and “non-overlapping.” Hint: If your fans sound like a jet engine, there’s a better way.

🔍 What’s Actually Going On

Pretend both lists are two tired robots, each barreling down their own lanes. They shine their interval-beams on the number line. If their spots overlap, that’s an intersection—snap a photo. The robot with the interval that finishes first scoots forward; once an interval ends, its robot is done seeing anything new. No double-backing, no existential crises. Bonus: these intervals are closed, so endpoints count. [4,4]? That’s an intersection too (even if it feels like a cruel joke).

🛠️ PseudoCode

• Start i and j at the beginning of both lists.
• While neither list is exhausted:
• Compare their intervals. Let’s say A[i] = [aStart, aEnd] and B[j] = [bStart, bEnd].
• Find the highest starting point: start = max(aStart, bStart)
• Find the lowest ending point: end = min(aEnd, bEnd)
• If start <= end, add [start, end] to results (don’t forget they can be equal!)
• Whoever’s interval ends first moves ahead:

  if (aEnd < bEnd) i++; else j++;

• Repeat until one robot runs out of juice. End scene.

💻 The Code

public List<int> intervalIntersection(int[][] A, int[][] B) {
    List<int> result = new ArrayList<>();
    int i = 0, j = 0;
    while (i < A.length && j < B.length) {
        int start = Math.max(A[i][0], B[j][0]);
        int end = Math.min(A[i][1], B[j][1]);
        if (start <= end) {
            result.add(new int[] { start, end });
        }
        if (A[i][1] < B[j][1]) i++;
        else j++;
    }
    return result;
}
</int></int>

⚠️ Pitfalls, Traps & Runtime Smacks

• Single-point overlaps: [7,7] is a valid intersection. If you skip this, interviewers will see right through you.
• No need to merge: Both lists are already in sorted, non-overlapping order. Wasting cycles merging is like alphabetizing your kitchen spices before DoorDash arrives.
• Nulls and empties: Don’t blow up at the end. Test for empty lists and handle them gracefully—unless you like exceptions at 11pm.
• Performance sanity: Both time and space are O(N+M). Unless you went wild with nested loops—then, enjoy your coffee-fueled all-nighter.

🧠 Interviewer Brain-Tattoo

“Sorted lists and two pointers: coffee for algorithms. Don’t nest what you can parallel—move fast, keep cool, and let those intervals do the hard work.”