MediumArraySortingUpdated Sep 2026

56. Merge Intervals

Asked at Amazon, Apple, Microsoft, Netflix and 14 more

Difficulty

Medium

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

18

Problem

You are given a list of intervals, each written as [start, end]. Merge every group of intervals that overlap, and return the merged list.

Two intervals overlap when one starts before the other ends. Touching intervals like [1,4] and [4,5] count as overlapping, so they merge into [1,5].

Overlapping intervals become one

input[1,3][2,6][8,10][15,18]output[1,6][8,10][15,18]
[1,3] and [2,6] share the stretch from 2 to 3, so they collapse into [1,6].

Constraints

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

Examples

Example 1
Inputintervals = [[1,3],[2,6],[8,10],[15,18]]
Output[[1,6],[8,10],[15,18]]
Why[1,3] and [2,6] overlap because 2 <= 3, so they merge into [1,6]. The other two touch nothing.
Example 2
Inputintervals = [[1,4],[4,5]]
Output[[1,5]]
WhyThey share the single point 4, which still counts as overlapping.
Example 3
Inputintervals = [[4,7],[1,4]]
Output[[1,7]]
WhyThe input is not sorted. After sorting by start, the same merge applies.

Asked At

18 companies
CompanyDifficulty
AmazonMediumView all Amazon questions →
AppleMediumView all Apple questions →
MicrosoftMediumView all Microsoft questions →
NetflixMediumView all Netflix questions →
OracleMediumView all Oracle questions →
UberMediumView all Uber questions →
AtlassianMediumView all Atlassian questions →
DatabricksMediumView all Databricks questions →
RipplingMediumView all Rippling questions →
SalesforceMediumView all Salesforce questions →
WalmartMediumView all Walmart questions →
BloombergMediumView all Bloomberg questions →
Goldman SachsMediumView all Goldman Sachs questions →
TikTokMediumView all TikTok questions →
LinkedInMediumView all LinkedIn questions →
VisaMediumView all Visa questions →
JPMorganMediumView all JPMorgan questions →
Capital OneMediumView all Capital One questions →

How to Think About It

1

Brute force: compare every pair of intervals to find overlaps. That's O(n²). You'd need to keep merging until no more overlaps exist. Tedious and slow.

2

Key insight: if you sort intervals by start time, all overlapping intervals become adjacent. You only need one pass through the sorted array to merge them.

3

Why sorting works: consider [[1,3],[2,6],[8,10]]. After sorting by start: [[1,3],[2,6],[8,10]]. Now [1,3] and [2,6] are adjacent — you can compare them directly. Without sorting, you'd have to check every pair.

4

The merge rule: after sorting, compare current interval's start with the last merged interval's end. If current start <= last end, they overlap — merge by extending last end to max(last end, current end). If current start > last end, no overlap — append current interval to result.

5

Edge cases: completely contained intervals like [1,10] and [2,5] — the max keeps the outer boundary. Back-to-back intervals like [1,3] and [3,5] — these overlap (3 <= 3). Single interval — return as-is.

Optimal Approach

Step 1: Sort intervals by start time.
Step 2: Initialize result with the first interval.
Step 3: For each subsequent interval:

  • Compare current start with last merged end
    - If they overlap (current start <= last end): extend last end to max(last end, current end)
  • If no overlap: append current interval to result

The key insight is that sorting guarantees overlapping intervals are adjacent. You never need to look back — just compare with the last merged interval.

Time: O(n log n) for sorting. Space: O(n) for the result array (O(log n) if you ignore output).

Sort by start, then sweep once

Sort intervals by startstart <= last.end ? extend last.endotherwise push a new blocksorted[1,3][2,6][8,10][15,18]2 <= 3 → extend end to 6last.end = max(last.end, current.end)never min — a short interval must not shrink the block
After sorting, an interval can only overlap the one merged block right before it.
ComplexityTime O(n log n)Space O(n)Sorting dominates; the merge pass itself is O(n). Space is the output list.

What Trips People Up in Real Interviews

1

Forgetting to sort first. Without sorting, you can't guarantee that overlapping intervals are adjacent. Sort by start time — this is the prerequisite for the O(n log n) merge pass.

2

Confusing "merge" with "check overlap." You need to merge intervals that overlap, not just identify them. Two intervals [a, b] and [c, d] overlap if c <= b (assuming sorted by start).

3

Not handling the case where one interval is entirely contained within another. If [1, 10] contains [2, 5], the merged result is [1, 10], not [1, 5].

4

Forgetting to add the last interval after the loop. The merge loop only adds intervals when it detects a non-overlap — the final interval is never compared, so add it manually.

5

Sorting by end time instead of start time. Sorting by end time doesn't guarantee overlapping intervals are adjacent — you need to sort by start time for the linear merge pass to work.

Solution Code

O(n log n) time
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Merge Intervals problem?

Given an array of intervals where each interval is a start and end pair, merge all overlapping intervals and return the non-overlapping result. This problem tests your ability to sort, compare, and handle edge cases cleanly.

How do you solve Merge Intervals?

The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Merge Intervals?

Merge Intervals is asked at Amazon, Apple, Microsoft, Netflix, Oracle, Uber, Atlassian, Databricks, Rippling, Salesforce, Walmart, Bloomberg, Goldman Sachs, TikTok, LinkedIn, Visa, JPMorgan, Capital One. It is a medium difficulty problem.

What are common mistakes on Merge Intervals?
  • Forgetting to sort first. Without sorting, you can't guarantee that overlapping intervals are adjacent. Sort by start time — this is the prerequisite for the `O(n log n)` merge pass.
  • Confusing "merge" with "check overlap." You need to merge intervals that overlap, not just identify them. Two intervals [a, b] and [c, d] overlap if c <= b (assuming sorted by start).
  • Not handling the case where one interval is entirely contained within another. If `[1, 10]` contains `[2, 5]`, the merged result is `[1, 10]`, not `[1, 5]`.
  • Forgetting to add the last interval after the loop. The merge loop only adds intervals when it detects a non-overlap — the final interval is never compared, so add it manually.
  • Sorting by end time instead of start time. Sorting by end time doesn't guarantee overlapping intervals are adjacent — you need to sort by start time for the linear merge pass to work.