Insert Interval

Medium Day 8 • Striver Blind 75

📌 Problem Overview

Insert newInterval into intervals (sorted non-overlapping) and merge if necessary.

Examples & Constraints

Example 1:

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

Constraints:

0 <= intervals.length <= 10^4

💡 Approach & Intuition

Three phases: add non-overlapping before, merge overlapping in middle, add non-overlapping after.

🎯 Pattern Recognition

Interval Manipulation

📊 Step-by-Step Execution (Mermaid Diagram)

graph TD
    Start["Input Data"] --> Process["Process Element by Element"]
    Process --> Lookup{"Hash Map / Set Lookup"}
    Lookup -- "Match Found" --> Return["Return Indices / Result"]
    Lookup -- "No Match" --> Store["Store in Map / Set"]
    Store --> Process

🐢 Brute Force Solution

Code

function insert(intervals, newInterval) {
  const res = [];
  let i = 0;
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    res.push(intervals[i++]);
  }
  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++;
  }
  res.push(newInterval);
  while (i < intervals.length) res.push(intervals[i++]);
  return res;
}

Time Complexity: O(n)
Space Complexity: O(n)
Explanation: Single pass interval merging.

⚡ Optimized Solution

Code

function insert(intervals, newInterval) {
  const res = [];
  let i = 0;
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    res.push(intervals[i++]);
  }
  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++;
  }
  res.push(newInterval);
  while (i < intervals.length) res.push(intervals[i++]);
  return res;
}

Time Complexity: O(n)
Space Complexity: O(n)
Explanation: O(n) linear sweep.

🐾 Step-by-Step Walkthrough

Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
Iterate & Evaluate: Process the input according to the boundary conditions.
Update & Return: Compute the optimal answer and return early or at termination.

🎙️ FAANG Interview Pitch

Push left non-overlapping, expand newInterval with overlapping, push right non-overlapping.

💡 Progressive Hints

Iterate through intervals and merge when overlap occurs.

⚡ Interactive Practice

👉 Solve this problem interactively in the DSA Lab