The O(n) Club: Insert Interval: The Algorithmic Family Reunion You’ll Never Escape

The O(n) Club: Insert Interval — The Algorithmic Family Reunion You’ll Never Escape

⚡ TL;DR

You’re handed a bunch of non-overlapping, neatly sorted intervals. Then someone barges in with a new interval and expects you to insert it in perfect order, keeping overlaps banned like open tabs in Chrome on low RAM. Brute force? Insert, sort, and merge like a frazzled intern. We can do better—one pass; zero emotional damage.

// The lazy approach: Insert, sort, then merge. Why create extra work? 
List<int> result = new ArrayList<>();
// There’s a wiser way…</int>

🧠 How Devs Usually Mess This Up

If you think merging intervals is like stacking pancakes, you’re close… except nobody merges pancakes mid-stack and expects syrup not to get everywhere. Common mistakes devs make include:

• Merging gone rogue: Either you merge way too early or miss overlaps, and now two meetings are fighting over the same conference room (good luck, HR).
• Insertion choreography: Painstakingly finding the exact position to shoehorn the new interval before merging—like searching for an empty seat at a sold-out cinema when everyone’s already watching the movie.
• Forgotten endings: Oops, didn’t add the new interval at the end if it never overlapped. (The ‘Uninvited’ interval deserves a seat too.)

🔍 What’s Actually Going On

Pretend your intervals are VIPs lined up at midnight for a new phone. Your new interval arrives, ticket in hand. It’ll:

• Wait patiently behind everyone (goes last—direct append);
• Elbow its way ahead if it’s early (direct insert at the front);
• Or, crash into a cluster and merge their time slots (take the minimum start and maximum end—the ‘peace treaty’).

Probably sounds like a sitcom episode, but you just need a single pass from left to right, herding intervals as you go. No need for sorting or index acrobatics.

🛠️ PseudoCode

• Set up a result list—this is your after-party guest list.
• March through all intervals:
  • If the current interval ends before the new one starts: just add it, no drama here.
  • If the current interval starts after the new one ends: time for the new interval to assert itself and join the guest list. Remember to add all remaining intervals too.
  • If there’s overlap: extend the new interval to cover everything — keep updating its start/end.
• If the new interval’s still solo after everyone else: add it at the end, don’t ghost it.

// Pseudo-Java (read: the coffee before code)
for (interval : intervals) {
  if (interval.end < newInterval.start)
    result.add(interval);
  else if (interval.start > newInterval.end) {
    result.add(newInterval);
    // add all leftovers, break
  } else {
    // Overlap! Update newInterval min(start), max(end)
  }
}
// If newInterval wasn’t added, toss it on the end.

💻 The Code

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int> merged = new ArrayList<>();
    int i = 0;
    // 1. Add intervals before newInterval
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        merged.add(intervals[i++]);
    }
    // 2. Merge overlaps
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    merged.add(newInterval);
    // 3. Add intervals after
    while (i < intervals.length) {
        merged.add(intervals[i++]);
    }
    return merged.toArray(new int[merged.size()][]);
}</int>

⚠️ Pitfalls, Traps & Runtime Smacks

• Off-by-one apocalypse: Always check if your interval should be added at the beginning or end.
• Merge-mania: Don’t merge unless necessary—just because intervals sit next to each other doesn’t mean they’re cozy.
• LeetCode List Trauma: Don’t forget to convert List<int[]> to int[][] (endless red errors if you do).
• Time/Space sanity: Single pass, O(n) time, O(n) space. If your run time mimics your last relationship — slow and full of drama — you did something wrong.

🧠 Interviewer Brain-Tattoo

“If you wouldn’t merge two family reunions, don’t merge two intervals unless they really overlap.”