Skip to content

Merge Intervals

Merge Intervals

Medium Day 8 • Striver Blind 75

📌 Problem Overview

Given an array of intervals, merge all overlapping intervals.

Examples & Constraints

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Constraints:

1 <= intervals.length <= 10^4

💡 Approach & Intuition

Sort intervals by start time, then merge adjacent intervals if curr.start <= prev.end.

🎯 Pattern Recognition

Sorting + Greedy Interval Merge

📊 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 merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const res = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    let last = res[res.length - 1];
    if (intervals[i][0] <= last[1]) last[1] = Math.max(last[1], intervals[i][1]);
    else res.push(intervals[i]);
  }
  return res;
}

Time Complexity: O(n log n)
Space Complexity: O(n)
Explanation: Sort and merge.

⚡ Optimized Solution

Code

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const res = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    let last = res[res.length - 1];
    if (intervals[i][0] <= last[1]) last[1] = Math.max(last[1], intervals[i][1]);
    else res.push(intervals[i]);
  }
  return res;
}

Time Complexity: O(n log n)
Space Complexity: O(n)
Explanation: Sort by start time and linear merge.

🐾 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

Sorting ensures overlapping intervals are contiguous in the list.

💡 Progressive Hints

Sort by start time first.

⚡ Interactive Practice

👉 Solve this problem interactively in the DSA Lab