131.Merge Intervals

MediumBlind 75Intervals · 2/6

Problem

Given an array intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover exactly the same points.

Intervals that share an endpoint ([1,4] and [4,5]) overlap and must be merged. The input is not sorted; the output may be in any order.

Examples

Input:  intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] overlap -> [1,6].

Input:  intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: They touch at 4, which counts as overlapping.

Input:  intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: Unsorted input — after ordering by start they touch at 4.

Constraints

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start_i <= end_i <= 10^4

💡 Key Insight

After sorting by start, any interval that overlaps the current merged block must come immediately after it — an interval that starts later than the block's end means no later interval (with an even larger start) can reach back into the block. So one sweep that either extends the last block's end or starts a new block is enough.

Brute Force (Repeated Pairwise Merge)

TimeO(n³)SpaceO(n)

Intuition

Keep merging any two overlapping intervals until no pair overlaps. Two intervals a, b overlap when a.start <= b.end && b.start <= a.end; their union is [min(starts), max(ends)].

Algorithm

Copy intervals into a list.
Repeat: scan all pairs (i, j); on the first overlapping pair, replace i with the union, remove j, and restart the scan.
Stop when a full scan finds no overlapping pair.

Visualization

[[1,3],[2,6],[8,10],[15,18]]
pass 1: (1,3) & (2,6) overlap -> [[1,6],[8,10],[15,18]]
pass 2: no overlapping pair -> done

Code

java

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

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        for (int[] in : intervals) {
            list.add(new int[] {in[0], in[1]});
        }
        boolean changed = true;
        while (changed) {
            changed = false;
            search:
            for (int i = 0; i < list.size(); i++) {
                for (int j = i + 1; j < list.size(); j++) {
                    int[] a = list.get(i), b = list.get(j);
                    if (a[0] <= b[1] && b[0] <= a[1]) { // overlap test
                        a[0] = Math.min(a[0], b[0]);
                        a[1] = Math.max(a[1], b[1]);
                        list.remove(j);
                        changed = true;
                        break search; // restart scan after a merge
                    }
                }
            }
        }
        return list.toArray(new int[0][]);
    }
}

Complexity

Time: O(n³) — up to n - 1 merges, each preceded by an O(n²) pair scan.
Space: O(n) — the working list.

Overlap Graph + Connected Components

TimeO(n²)SpaceO(n²)

Intuition

Treat each interval as a node and connect two nodes if their intervals overlap. Each connected component merges into one interval spanning the minimum start to the maximum end of its members — even if two members don't directly overlap, a chain of overlaps links them.

Algorithm

Build adjacency lists by testing all n²/2 pairs for overlap.
For every unvisited node, DFS to collect its component, tracking minStart and maxEnd.
Emit [minStart, maxEnd] per component.

Visualization

flowchart LR
    A["[1,3]"] --- B["[2,6]"]
    C["[8,10]"]
    D["[15,18]"]
    B --> R1["component 1 -> [1,6]"]
    C --> R2["component 2 -> [8,10]"]
    D --> R3["component 3 -> [15,18]"]

Code

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (intervals[i][0] <= intervals[j][1] && intervals[j][0] <= intervals[i][1]) {
                    graph.get(i).add(j);
                    graph.get(j).add(i);
                }
            }
        }
        boolean[] visited = new boolean[n];
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                continue;
            }
            int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(i);
            visited[i] = true;
            while (!stack.isEmpty()) { // DFS over one component
                int cur = stack.pop();
                lo = Math.min(lo, intervals[cur][0]);
                hi = Math.max(hi, intervals[cur][1]);
                for (int next : graph.get(cur)) {
                    if (!visited[next]) {
                        visited[next] = true;
                        stack.push(next);
                    }
                }
            }
            result.add(new int[] {lo, hi});
        }
        return result.toArray(new int[0][]);
    }
}

Complexity

Time: O(n²) — building the graph checks every pair; the DFS is O(n + E).
Space: O(n²) — the adjacency lists in the worst case (all intervals overlap).

Sort and SweepOptimal

TimeO(n log n)SpaceO(n)

Intuition

Sort by start. Keep the last merged block. For each next interval, if it starts at or before the block's end, it overlaps — extend the end with max (it might be fully contained, so don't just overwrite). Otherwise there is a gap and it begins a new block.

Algorithm

Sort intervals by start.
For each interval cur:
- If merged is empty or last[1] < cur[0]: append a copy of cur.
- Else: last[1] = max(last[1], cur[1]).
Return merged as an array.

Dry Run

flowchart TD
    S["sorted: [1,3] [2,6] [8,10] [15,18]"] --> A["take [1,3]<br/>merged = [[1,3]]"]
    A --> B{"2 <= 3?"}
    B -->|"yes: end = max(3,6)"| C["merged = [[1,6]]"]
    C --> D{"8 <= 6?"}
    D -->|"no: new block"| E["merged = [[1,6],[8,10]]"]
    E --> F{"15 <= 10?"}
    F -->|"no: new block"| G["[[1,6],[8,10],[15,18]]"]

Code

java

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

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();
        for (int[] cur : intervals) {
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < cur[0]) {
                merged.add(new int[] {cur[0], cur[1]}); // gap before cur: new block
            } else {
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], cur[1]); // overlap: extend (cur may be nested)
            }
        }
        return merged.toArray(new int[0][]);
    }
}

Complexity

Time: O(n log n) — sorting; the sweep is O(n).
Space: O(n) — the output list, plus O(log n) for sorting.

Complexity Comparison

Approach	Time	Space
Repeated Pairwise Merge	O(n³)	O(n)
Overlap Graph + Components	O(n²)	O(n²)
Sort and Sweep	O(n log n)	O(n)

Common Pitfalls

Setting last[1] = cur[1] instead of max(last[1], cur[1]) — breaks on nested intervals like [1,10],[2,3].
Using < vs <= wrongly: [1,4],[4,5] must merge, so a new block starts only when last[1] < cur[0].
Forgetting to sort — the input order is arbitrary.
Comparator a[0] - b[0] is safe for these bounds but can overflow with large negatives; Integer.compare avoids that.