What is the brute force approach and complexity for Merge Intervals?

Scan all pairs, merge the first overlapping pair found, repeat with time complexity O(N³) and space complexity O(N).

What is the optimal approach and complexity for Merge Intervals?

Sort by start; each interval either stretches the last group or starts a new one with optimal time complexity O(N log N) and space complexity O(N).

How do you identify the pattern for Merge Intervals?

Look for key signals in the prompt: "list of [start, end] intervals" indicates Interval problem → think about sorting by start or by end.; "merge all overlapping" indicates Groups of intervals that chain together. After sorting by start, a group is a run of neighbours.; "any order is fine" indicates We are free to sort the input; nothing depends on the original order..

Merge Intervals

Medium·LeetCode #56Basic Anchor

LeetCode

Jump:

30-Second Mental ModelIntervals — Merge overlaps

Complexity:O(N³)→O(N log N)

Key Insight

Sort by start. Walk through the intervals keeping a list merged. If the current interval starts at or before the end of merged.back(), it overlaps that group: stretch the group's end to max(end, cur.end). Otherwise it starts a new group.

Core Validity Invariant

cur joins the last group if and only if cur.start ≤ merged.back().end.

Problem

You get a list of intervals. Each one is [start, end] and includes both ends.

If two intervals overlap, join them into one bigger interval. Keep doing this until no two intervals overlap. Return the final list.

Intervals that only touch (one ends exactly where the next starts, like [1,4] and [4,5]) also count as overlapping and must be joined.

Input

A list intervals, where intervals[i] = [start, end].

Output

The merged intervals, with no two overlapping. Any order is accepted.

Example 1

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

Output: [[1,6],[8,10],[15,18]]

[1,3] and [2,6] overlap (2 is inside [1,3]), so they become [1,6]. The other two don't touch anything.

Example 2

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

They share the point 4, which counts as overlapping.

Example 3

Input: intervals = [[4,7],[1,4]]

Output: [[1,7]]

The input is not sorted. [1,4] and [4,7] touch at 4, so they join.

Constraints

• 1 ≤ intervals.length ≤ 10^4
• intervals[i].length == 2
• 0 ≤ start ≤ end ≤ 10^4

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
When exactly do two intervals [a, b] and [c, d] overlap? Write the test with ≤ or < and check it on touching intervals.
2.
If the input were sorted by start, where would the intervals that overlap a given one be?
3.
When I join two intervals, what is the new start and the new end?
4.
Can one interval sit completely inside another? What happens to the end then?
5.
Once an interval starts after my current group ends, can any later interval still join that group?

Brute force approach

Idea

Copy the list. Look at every pair of intervals. As soon as two of them overlap, replace them with one interval [min start, max end] and start scanning again. When a full scan finds no overlapping pair, we are done.

Thinking process

1
The problem says: join overlapping intervals until no two overlap. The most direct way is to do exactly that.
2
Two intervals overlap when each one starts before the other ends: a.start ≤ b.end && b.start ≤ a.end.
3
After a merge the new, bigger interval may now overlap something it didn't before, so I scan again from the beginning.
4
Each merge removes one interval, so there are at most n − 1 merges.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> list = intervals;

        // Keep merging any two overlapping intervals until no pair overlaps.
        bool changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < (int)list.size() && !changed; i++) {
                for (int j = i + 1; j < (int)list.size() && !changed; j++) {
                    // Two intervals overlap when each one starts before the other ends.
                    // Touching ends (like [1,2] and [2,3]) count as overlapping.
                    if (list[i][0] <= list[j][1] && list[j][0] <= list[i][1]) {
                        list[i] = {min(list[i][0], list[j][0]), max(list[i][1], list[j][1])};
                        list.erase(list.begin() + j);
                        changed = true;  // the list changed, so scan again from the start
                    }
                }
            }
        }
        return list;
    }
};

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

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        for (int[] interval : intervals) {
            list.add(new int[] { interval[0], interval[1] });
        }

        // Keep merging any two overlapping intervals until no pair overlaps.
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < list.size() && !changed; i++) {
                for (int j = i + 1; j < list.size() && !changed; j++) {
                    // Two intervals overlap when each one starts before the other ends.
                    // Touching ends (like [1,2] and [2,3]) count as overlapping.
                    if (list.get(i)[0] <= list.get(j)[1] && list.get(j)[0] <= list.get(i)[1]) {
                        list.get(i)[0] = Math.min(list.get(i)[0], list.get(j)[0]);
                        list.get(i)[1] = Math.max(list.get(i)[1], list.get(j)[1]);
                        list.remove(j);
                        changed = true; // the list changed, so scan again from the start
                    }
                }
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        res = [list(interval) for interval in intervals]

        # Keep merging any two overlapping intervals until no pair overlaps.
        changed = True
        while changed:
            changed = False
            for i in range(len(res)):
                for j in range(i + 1, len(res)):
                    # Two intervals overlap when each one starts before the other ends.
                    # Touching ends (like [1,2] and [2,3]) count as overlapping.
                    if res[i][0] <= res[j][1] and res[j][0] <= res[i][1]:
                        res[i] = [min(res[i][0], res[j][0]), max(res[i][1], res[j][1])]
                        res.pop(j)
                        changed = True
                        break
                if changed:
                    break
        return res

export function merge(intervals: number[][]): number[][] {
    const list: number[][] = intervals.map(interval => [...interval]);

    // Keep merging any two overlapping intervals until no pair overlaps.
    let changed = true;
    while (changed) {
        changed = false;
        for (let i = 0; i < list.length && !changed; i++) {
            for (let j = i + 1; j < list.length && !changed; j++) {
                // Two intervals overlap when each one starts before the other ends.
                // Touching ends (like [1,2] and [2,3]) count as overlapping.
                if (list[i][0] <= list[j][1] && list[j][0] <= list[i][1]) {
                    list[i] = [Math.min(list[i][0], list[j][0]), Math.max(list[i][1], list[j][1])];
                    list.splice(j, 1);
                    changed = true;
                }
            }
        }
    }
    return list;
}

Complexity

Time O(N³)Space O(N)

Each scan checks up to N² pairs, and there can be N − 1 merges, each followed by a fresh scan. Erasing from the middle of the vector also costs O(N). With N = 10^4, that is far too slow.

Optimized approach

Idea

Start from brute force

Brute force compares every interval with every other interval, again and again, because it has no idea where the overlapping ones are.

Find the repeated work

Each fresh scan rechecks pairs that were already known not to overlap. The real problem is the order: overlapping intervals can be anywhere in the list. Sorting by start fixes that.

Define the state — what variables do I need?

merged: The groups built so far. All but the last one are finished.
merged.back(): The group being built right now: its start is fixed, its end can still grow.
cur: The next interval in sorted order.

Define validity

cur joins the last group if and only if cur.start ≤ merged.back().end.

Define the transitions — when does each pointer move, and why is it safe?

cur.start ≤ merged.back().end

merged.back().end = max(merged.back().end, cur.end)

cur starts inside the group (or exactly at its end), so they overlap. The group's start is already the smaller one because of sorting. The end becomes whichever reaches further — cur may be completely inside the group.

cur.start > merged.back().end (or merged is empty)

merged.push_back(cur)

There is a gap. Every later interval starts at or after cur.start, so also after the gap. Nothing can ever join the old group again, so it is final.

What does the current window add to the answer?

Each interval either stretches the last group or opens a new one. When the pass ends, every group in merged is final.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // After sorting by start, any interval that overlaps the current
        // group must come right after it.
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> merged;
        for (auto& cur : intervals) {
            if (!merged.empty() && cur[0] <= merged.back()[1]) {
                // Overlaps the last merged interval: stretch its end.
                // Use max, because cur may sit completely inside it.
                merged.back()[1] = max(merged.back()[1], cur[1]);
            } else {
                // Starts after the last merged interval ends: a new group begins.
                merged.push_back(cur);
            }
        }
        return merged;
    }
};

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

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;

        // After sorting by start, any interval that overlaps the current
        // group must come right after it.
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();
        for (int[] cur : intervals) {
            if (!merged.isEmpty() && cur[0] <= merged.get(merged.size() - 1)[1]) {
                // Overlaps the last merged interval: stretch its end.
                // Use max, because cur may sit completely inside it.
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], cur[1]);
            } else {
                // Starts after the last merged interval ends: a new group begins.
                merged.add(new int[] { cur[0], cur[1] });
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        # After sorting by start, any interval that overlaps the current
        # group must come right after it.
        intervals.sort(key=lambda x: x[0])

        merged: list[list[int]] = []
        for cur in intervals:
            if merged and cur[0] <= merged[-1][1]:
                # Overlaps the last merged interval: stretch its end.
                # Use max, because cur may sit completely inside it.
                merged[-1][1] = max(merged[-1][1], cur[1])
            else:
                # Starts after the last merged interval ends: a new group begins.
                merged.append(cur)

        return merged

export function merge(intervals: number[][]): number[][] {
    // After sorting by start, any interval that overlaps the current
    // group must come right after it.
    intervals.sort((a, b) => a[0] - b[0]);

    const merged: number[][] = [];
    for (const cur of intervals) {
        if (merged.length > 0 && cur[0] <= merged[merged.length - 1][1]) {
            // Overlaps the last merged interval: stretch its end.
            // Use max, because cur may sit completely inside it.
            merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], cur[1]);
        } else {
            // Starts after the last merged interval ends: a new group begins.
            merged.push([...cur]);
        }
    }
    return merged;
}

Complexity

Time O(N log N)Space O(N)

Sorting is O(N log N); the pass is O(N). The output list can hold N intervals, and sorting uses O(log N) extra stack.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Scan all pairs, merge the first overlapping pair found, repeat	O(N³)	O(N)
Optimal	Sort by start; each interval either stretches the last group or starts a new one	O(N log N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“list of [start, end] intervals”Interval problem → think about sorting by start or by end.
“merge all overlapping”Groups of intervals that chain together. After sorting by start, a group is a run of neighbours.
“any order is fine”We are free to sort the input; nothing depends on the original order.

[start, end] pairs+join overlaps+sort by start, compare with the last group→Intervals — Merge overlaps

This is the anchor for the whole Merge sub-pattern: sort by start, keep one running group, and decide with a single test cur.start ≤ end. The next questions change only small parts: Insert Interval skips the sort because the input is already sorted, Remove Covered Intervals changes the test to containment, and Count Days Without Meetings adds up the merged lengths.

Don't make this mistake

Comparing with intervals[i − 1] instead of the last merged interval

✗ if (intervals[i][0] <= intervals[i - 1][1]) ...

✓ if (cur[0] <= merged.back()[1]) ...

The previous interval can be short while the group is long. In [1,10], [2,3], [5,6], the interval [5,6] does not overlap [2,3], but it does overlap the group [1,10]. Always compare with the group, not the neighbour.

Setting end = cur.end instead of the max

✗ merged.back()[1] = cur[1];

✓ merged.back()[1] = max(merged.back()[1], cur[1]);

An interval can sit completely inside the group. With [1,6], [4,5], writing end = 5 shrinks the group, and a later [6,7] would wrongly become its own group.

Using < instead of ≤ for the overlap test

✗ if (cur[0] < merged.back()[1])

✓ if (cur[0] <= merged.back()[1])

Here touching intervals like [1,4] and [4,5] must join. With < they stay apart.

Pattern confusion: sorting by end

Sorting by end is the trick for the Coverage sub-pattern (Non-overlapping Intervals, Arrows), where you greedily keep the earliest finisher. For merging, sort by start: a long interval like [1,10] sorted by end comes after [2,3] and [5,6]. Those two become separate groups first, then [1,10] only joins the last one, giving the wrong answer [[2,3],[5,10]] instead of [[1,10]].

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Intervals translate into production architectures and low-level memory mechanics.

LLD Architecture