300. Insert Interval

🔗 LeetCode Problem: 57. Insert Interval
📊 Difficulty: Medium
🏷️ Topics: Array

Problem Statement

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: Because the new interval [2,5] overlaps with [1,3], we merge them into [1,5].

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10], we merge them into [3,10].

Constraints: - 0 <= intervals.length <= 10^4 - intervals[i].length == 2 - 0 <= starti <= endi <= 10^5 - intervals is sorted by starti in ascending order - newInterval.length == 2 - 0 <= start <= end <= 10^5

---

🌳 Visual Understanding - The Insert Problem

The Problem We're Solving:

Existing intervals (sorted, non-overlapping):
  [1, 3]     [6, 9]
  |---|      |---|

New interval to insert: [2, 5]
               |---|

Insertion result:
  [2, 5] overlaps with [1, 3]
  Merge them: [1, 5]

  [6, 9] doesn't overlap with [1, 5]
  Keep separate

Final: [[1, 5], [6, 9]]

Key Observations:

1. Input is ALREADY SORTED by start time
   Don't need to sort!

2. Input intervals are NON-OVERLAPPING
   No overlaps exist before insertion!

3. newInterval might overlap with MULTIPLE intervals
   Example: [4,8] overlaps with [3,5], [6,7], [8,10]
   Must merge all of them!

4. Three types of intervals to handle:
   a) Intervals BEFORE newInterval (no overlap)
   b) Intervals OVERLAPPING with newInterval (merge)
   c) Intervals AFTER newInterval (no overlap)

Visual Discovery:

Example: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
         newInterval = [4,8]

Timeline:
  [1,2]  [3,5]  [6,7]  [8,10]  [12,16]
  |--|   |--|   |--|   |----|   |-----|
           [4,      8]
           |--------|

Analysis:
  [1,2]: ends at 2, newInterval starts at 4
         2 < 4, so NO overlap → Keep before

  [3,5]: starts at 3, ends at 5
         Overlaps with [4,8] → Merge

  [6,7]: Overlaps with [4,8] → Merge

  [8,10]: starts at 8, overlaps with [4,8] (touching) → Merge

  [12,16]: starts at 12, newInterval ends at 8
           12 > 8, so NO overlap → Keep after

Merged result: [3, 10] (merged [3,5], [6,7], [8,10] with [4,8])

Final: [[1,2], [3,10], [12,16]]

---

🧠 The AHA Moment - Three-Phase Scan

Approach 1: Use Merge Intervals Logic (Good)

Simple approach:
  1. Add newInterval to intervals
  2. Sort the array
  3. Use merge intervals algorithm

Time: O(n log n) due to sorting

Works, but we can do BETTER!
We're given sorted input - why sort again? 🤔

Approach 2: Linear Scan (Optimal)

Key insight: Input is ALREADY SORTED!

We can scan once and handle three phases:

Phase 1: Add all intervals that end BEFORE newInterval starts
  These come before, no overlap possible

Phase 2: Merge all intervals that OVERLAP with newInterval
  Keep extending newInterval to cover all overlaps

Phase 3: Add all remaining intervals
  These come after, no overlap possible

Time: O(n) - Single pass!
Space: O(1) (excluding output)

This is OPTIMAL! 🎯

Visual Discovery of Three Phases:

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 1: Intervals BEFORE newInterval
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

[1,2]: ends at 2, newInterval starts at 4
  2 < 4? YES → Add [1,2] to result

[3,5]: ends at 5, newInterval starts at 4
  5 < 4? NO → Stop Phase 1

Result so far: [[1,2]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 2: Intervals OVERLAPPING with newInterval
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Start with: newInterval = [4, 8]

[3,5]: Does it overlap?
  newInterval.start (4) <= interval.end (5)? YES
  Merge: newInterval.start = min(4, 3) = 3
         newInterval.end = max(8, 5) = 8
  newInterval = [3, 8]

[6,7]: Does it overlap?
  newInterval.start (3) <= interval.end (7)? YES (because 3 < 7)
  Wait, better check: interval.start (6) <= newInterval.end (8)? YES
  Merge: newInterval.start = min(3, 6) = 3
         newInterval.end = max(8, 7) = 8
  newInterval = [3, 8]

[8,10]: Does it overlap?
  interval.start (8) <= newInterval.end (8)? YES (touching!)
  Merge: newInterval.start = min(3, 8) = 3
         newInterval.end = max(8, 10) = 10
  newInterval = [3, 10]

[12,16]: Does it overlap?
  interval.start (12) <= newInterval.end (10)? NO
  Stop Phase 2

Add merged newInterval: [3, 10]

Result so far: [[1,2], [3,10]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 3: Intervals AFTER newInterval
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

[12,16]: Add to result

Result: [[1,2], [3,10], [12,16]] ✓

---

🔴 Approach 1: Add + Sort + Merge (Simple but not optimal)

💡 Intuition

Reuse Merge Intervals solution:
  1. Add newInterval to intervals array
  2. Sort by start time
  3. Apply merge intervals algorithm

Straightforward but sorts already-sorted input!

📝 Implementation

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        // Create new array with space for newInterval
        int[][] all = new int[intervals.length + 1][2];

        // Copy existing intervals
        for (int i = 0; i < intervals.length; i++) {
            all[i] = intervals[i];
        }
        all[intervals.length] = newInterval;

        // Sort by start time
        Arrays.sort(all, (a, b) -> a[0] - b[0]);

        // Merge intervals (same as Problem 299)
        List<int[]> merged = new ArrayList<>();
        int[] current = all[0];

        for (int i = 1; i < all.length; i++) {
            if (current[1] >= all[i][0]) {
                current[1] = Math.max(current[1], all[i][1]);
            } else {
                merged.add(current);
                current = all[i];
            }
        }
        merged.add(current);

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

📊 Complexity Analysis

Time Complexity: O(n log n)

Create new array: O(n)
Sort: O(n log n)
Merge: O(n)
Total: O(n log n)

Works but not optimal for sorted input!

Space Complexity: O(n)

Temporary array: O(n)
Result list: O(n)

---

🟢 Approach 2: Linear Scan - Three Phases (Optimal)

🎨 Building the Complete Solution

The Three-Phase Strategy:

Phase 1: Add intervals BEFORE newInterval
  While interval.end < newInterval.start:
    Add interval to result
    These definitely don't overlap!

Phase 2: Merge intervals that OVERLAP with newInterval
  While interval.start <= newInterval.end:
    Merge: newInterval.start = min(newInterval.start, interval.start)
           newInterval.end = max(newInterval.end, interval.end)
    Keep expanding newInterval!

  After loop: Add merged newInterval to result

Phase 3: Add intervals AFTER newInterval
  Add all remaining intervals to result
  These come after, no overlap!

📝 Implementation - Clean and Efficient

import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        // Phase 1: Add all intervals that come before newInterval
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // Phase 2: Merge all overlapping intervals with newInterval
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);  // Add the merged interval

        // Phase 3: Add all intervals that come after newInterval
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

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

🔍 Complete Dry Run - Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]

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

result = []
i = 0
newInterval = [2, 5]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 1: Add intervals BEFORE newInterval
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Check intervals[0] = [1,3]:
  interval.end < newInterval.start?
  3 < 2? NO

  Stop Phase 1 (no intervals added)

i = 0
result = []

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 2: Merge OVERLAPPING intervals
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Check intervals[0] = [1,3]:
  interval.start <= newInterval.end?
  1 <= 5? YES → Overlap!

  Merge:
    newInterval[0] = min(2, 1) = 1
    newInterval[1] = max(5, 3) = 5
    newInterval = [1, 5]

  i = 1

Check intervals[1] = [6,9]:
  interval.start <= newInterval.end?
  6 <= 5? NO

  Stop Phase 2

Add merged newInterval [1,5] to result

i = 1
result = [[1,5]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 3: Add intervals AFTER newInterval
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Add intervals[1] = [6,9]
i = 2

result = [[1,5], [6,9]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Return: [[1,5], [6,9]] ✓

Complete Dry Run - Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
       newInterval = [4,8]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 1: Intervals BEFORE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

intervals[0] = [1,2]:
  2 < 4? YES
  Add [1,2] to result
  i = 1

intervals[1] = [3,5]:
  5 < 4? NO
  Stop Phase 1

result = [[1,2]]
i = 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 2: OVERLAPPING intervals
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

intervals[1] = [3,5]:
  3 <= 8? YES
  Merge: newInterval = [min(4,3), max(8,5)] = [3, 8]
  i = 2

intervals[2] = [6,7]:
  6 <= 8? YES
  Merge: newInterval = [min(3,6), max(8,7)] = [3, 8]
  i = 3

intervals[3] = [8,10]:
  8 <= 8? YES (touching!)
  Merge: newInterval = [min(3,8), max(8,10)] = [3, 10]
  i = 4

intervals[4] = [12,16]:
  12 <= 10? NO
  Stop Phase 2

Add [3,10] to result

result = [[1,2], [3,10]]
i = 4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PHASE 3: Intervals AFTER
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Add intervals[4] = [12,16]
i = 5

result = [[1,2], [3,10], [12,16]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Return: [[1,2], [3,10], [12,16]] ✓

Edge Cases

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
EDGE CASE 1: Empty intervals
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

intervals = [], newInterval = [5,7]

Phase 1: Skip (no intervals)
Phase 2: Skip (no intervals)
  Add newInterval [5,7]
Phase 3: Skip (no intervals)

Result: [[5,7]] ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
EDGE CASE 2: newInterval at the beginning
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

intervals = [[3,5],[6,9]], newInterval = [1,2]

Phase 1: 
  [3,5]: 5 < 1? NO → Stop
  (nothing added)

Phase 2:
  [3,5]: 3 <= 2? NO → Stop
  Add [1,2]

Phase 3:
  Add [3,5], [6,9]

Result: [[1,2], [3,5], [6,9]] ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
EDGE CASE 3: newInterval at the end
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

intervals = [[1,2],[3,5]], newInterval = [6,9]

Phase 1:
  [1,2]: 2 < 6? YES → Add
  [3,5]: 5 < 6? YES → Add

Phase 2:
  No intervals left → Add [6,9]

Phase 3:
  No intervals left

Result: [[1,2], [3,5], [6,9]] ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
EDGE CASE 4: newInterval covers all
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

intervals = [[3,5],[6,7]], newInterval = [1,10]

Phase 1:
  [3,5]: 5 < 1? NO → Stop

Phase 2:
  [3,5]: 3 <= 10? YES → Merge → [1,10]
  [6,7]: 6 <= 10? YES → Merge → [1,10]

Phase 3:
  No intervals left

Result: [[1,10]] ✓

📊 Complexity Analysis

Time Complexity: O(n)

Single pass through intervals
Each interval visited once
Three phases combined: O(n)

OPTIMAL! Can't do better than linear! 🎯

Space Complexity: O(1)

Excluding output space
Only using a few variables (i, newInterval)

Output space: O(n) for result array
But this doesn't count in space complexity

---

🎯 Key Insights Summary

The Three Critical Points:

1. Three-Phase Linear Scan

Phase 1: Before (no overlap possible)
Phase 2: Overlapping (merge them)
Phase 3: After (no overlap possible)

This structure naturally handles all cases! 🔑

2. Leverage Sorted Input

Input is already sorted!
Don't resort - waste of time!

Use single linear scan instead
O(n) vs O(n log n)

This is THE optimization! 🎯

3. Merge Condition

Interval overlaps with newInterval if:
  interval.start <= newInterval.end

AND we're in Phase 2 (haven't passed newInterval yet)

When to stop merging?
  When interval.start > newInterval.end

---

💡 Why This Approach Works - Deep Intuition

Why Three Phases Are Sufficient:

Key property: Input is SORTED by start time

This means:
  1. All intervals with end < newInterval.start
     come BEFORE newInterval (Phase 1)

  2. All intervals that might overlap
     are CONSECUTIVE in the sorted array (Phase 2)

  3. All intervals with start > newInterval.end
     come AFTER newInterval (Phase 3)

No interval can "jump over" newInterval!
Therefore: Single pass handles everything! ✓

Why We Modify newInterval During Phase 2:

As we merge, newInterval GROWS:

Start: newInterval = [4, 8]

Merge with [3,5]: newInterval = [3, 8]
  Now extends further left!

Merge with [6,7]: newInterval = [3, 8]
  Contained, no change

Merge with [8,10]: newInterval = [3, 10]
  Now extends further right!

Growing newInterval allows it to "capture" more intervals
This handles chains of overlaps automatically! 🎯

---

⚠️ Common Mistakes

// Mistake 1: Wrong Phase 1 condition
while (i < n && intervals[i][1] <= newInterval[0]) { // ❌ Should be <
// ✓ CORRECT: Touching should merge in Phase 2
while (i < n && intervals[i][1] < newInterval[0]) {

// Mistake 2: Wrong Phase 2 condition
while (i < n && intervals[i][0] < newInterval[1]) { // ❌ Should be <=
// ✓ CORRECT: Touching intervals should merge
while (i < n && intervals[i][0] <= newInterval[1]) {

// Mistake 3: Forgetting to add merged newInterval
// After Phase 2 loop
// ❌ Forgot: result.add(newInterval);
// ✓ CORRECT: Must add after Phase 2!
result.add(newInterval);

// Mistake 4: Not using min/max when merging
newInterval[0] = intervals[i][0]; // ❌ Might be larger!
// ✓ CORRECT:
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);

// Mistake 5: Unnecessary sorting
Arrays.sort(intervals, ...); // ❌ Already sorted!
// ✓ CORRECT: Don't sort! Use linear scan!

---

🎓 Comparison of Approaches

┌────────────────────┬─────────────┬────────────┬──────────────┐
│ Approach           │ Time        │ Space      │ Difficulty   │
├────────────────────┼─────────────┼────────────┼──────────────┤
│ Add + Sort + Merge │ O(n log n)  │ O(n)       │ Easy to code │
│ Three-Phase Scan   │ O(n)        │ O(1)       │ Need insight │
└────────────────────┴─────────────┴────────────┴──────────────┘

Three-Phase is optimal but requires understanding!
Add + Sort + Merge is acceptable but not optimal!

In interview:
  - Start with Add + Sort approach (shows you know Merge Intervals)
  - Then optimize: "Input is sorted - can we avoid sorting?"
  - Present Three-Phase approach

This shows problem-solving progression! 💯

---

📝 Quick Revision Notes

🎯 Core Concept

Problem: Insert interval into sorted non-overlapping intervals

Key Insight: Input sorted - use THREE-PHASE linear scan!

Algorithm: 1. Phase 1: Add intervals ending before newInterval 2. Phase 2: Merge intervals overlapping with newInterval 3. Phase 3: Add intervals starting after newInterval

Why It Works: Sorted input guarantees phases are consecutive!

⚡ Quick Implementation

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

public class Solution {
  public int[][] insert(int[][] intervals, int[] newInterval) {
    // return sortAndMerge(intervals, newInterval);
    return linear(intervals, newInterval);
  }

  private int[][] linear(int[][] intervals, int[] newInterval) {
    // { 1, 2 }, { 3, 5 }, { 6, 7 }, { 8, 10 }, { 12, 16 } and { 4, 8 }
    List<int[]> list = new ArrayList<>();
    int i = 0;
    int n = intervals.length;

    // step 1: process all intervals coming before to this new interval
    while (i < n && intervals[i][1] < newInterval[0]) {
      list.add(intervals[i]);
      i++;
    }

    // step 2: process all intervals that may merge with this new interval
    while (i < n) {
      // GOTCHA: different from our natural thinking (ONLY if condition)
      if (intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
        newInterval[1] = Math.max(intervals[i][1], newInterval[1]);

        System.out.println(Arrays.toString(newInterval));
        i++;
      } else {
        break;
      }
    }
    list.add(newInterval);

    // step 3: process remaining intervals which come after this new interval
    while (i < n) {
      list.add(intervals[i]);
      i++;
    }

    // step 4: covert to array
    return list.toArray(new int[list.size()][]);
  }

  public int[][] sortAndMerge(int[][] intervals, int[] newInterval) {
    // step 0: keep this newInterval in main array intervals itself
    int n = intervals.length;
    int[][] a = new int[n + 1][2];

    for (int i = 0; i < n; i++) {
      a[i][0] = intervals[i][0];
      a[i][1] = intervals[i][1];
    }

    a[n][0] = newInterval[0];
    a[n][1] = newInterval[1];

    // From here, everything is same as earlier problem
    // https://leetcode.com/problems/merge-intervals/

    // step 1: sort by start time
    Arrays.sort(a, (m1, m2) -> m1[0] - m2[0]);

    // step 2: go through all meetings
    List<int[]> list = new ArrayList<>();
    list.add(new int[] { a[0][0], a[0][1] });

    for (int i = 1; i < a.length; i++) {
      int[] prev = list.get(list.size() - 1);
      int[] curr = a[i];

      if (curr[0] >= prev[0] && curr[0] <= prev[1]) {
        // if curr meeting falls in between prev meeting, include it.
        int max = Math.max(prev[1], curr[1]);
        list.remove(list.size() - 1);
        list.add(new int[] { prev[0], max });
      } else {
        // else add it as a new entry
        list.add(curr);
      }
    }

    // step 3: convert this list to array
    int size = list.size();
    int[][] res = new int[size][2];
    for (int i = 0; i < size; i++) {
      res[i][0] = list.get(i)[0];
      res[i][1] = list.get(i)[1];
    }

    return res;
  }

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

    // [[1,5],[6,9]]
    System.out.println(Arrays.deepToString(s.insert(new int[][] { { 1, 3 }, { 6, 9 } }, new int[] { 2, 5 })));
    // [[1,2],[3,10],[12,16]]
    System.out.println(Arrays.deepToString(
        s.insert(new int[][] { { 1, 2 }, { 3, 5 }, { 6, 7 }, { 8, 10 }, { 12, 16 } }, new int[] { 4, 8 })));
  }
}

🔑 Key Points

✓ Input already sorted - don't resort!
✓ Three phases: before, merge, after
✓ Phase 1 condition: end < newStart
✓ Phase 2 condition: start <= newEnd
✓ Grow newInterval as you merge
✓ Don't forget to add newInterval after Phase 2!
✓ Time: O(n), Space: O(1) - OPTIMAL!

🎪 Memory Aid

"Three phases clear, sorted input's here!"
"Before, merge, after - no fear!"
"Less than start? Phase one appear!"
"Less equals end? Phase two, stay near!" ✨

---

🎉 Congratulations!

You've mastered Insert Interval!

What You Learned:

✅ Three-phase linear scan - Optimal pattern
✅ Leverage sorted input - Don't resort!
✅ Growing interval during merge - Dynamic extension
✅ Two approaches - Simple and optimal
✅ Interview progression - From brute to optimal

The Beautiful Insight:

Sorted Input → Linear Solution Possible!

The core insight:
  "Input is sorted - why resort?"
  "Phases are naturally consecutive!"

  Three-Phase Strategy:
    Before: Definitely no overlap (ends before)
    Merge: Might overlap (check and merge)
    After: Definitely no overlap (starts after)

  Single pass handles all cases!

This pattern of "leveraging sorted input" appears in:
  - Binary search problems
  - Two pointer problems
  - Merge operations
  - Many interval problems

Master this = Recognize optimization opportunities! ✨

Interview Mastery:

When asked about Insert Interval:

1. Understand: "Insert into sorted non-overlapping intervals"

2. Clarify: "Touching intervals merge, right?"

3. Simple approach: "Could add newInterval, sort, then merge.
   That's O(n log n)."

4. Key observation: "But input is already sorted!
   Can we avoid sorting?"

5. Optimal insight: "Yes! Use three-phase linear scan:
   - Phase 1: Add intervals before newInterval
   - Phase 2: Merge overlapping intervals
   - Phase 3: Add intervals after newInterval"

6. Why it works: "Sorted input guarantees phases consecutive.
   Single pass handles everything!"

7. Code it: Clean O(n) solution

8. Complexity: "O(n) time, O(1) space excluding output.
   Can't do better than linear!"

Shows complete progression from simple to optimal! 💯

You've mastered problem 300! This problem teaches the valuable lesson of leveraging pre-sorted input! 🚀✨🎯