30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 56. Merge Intervals

Given a list of intervals, merge all overlapping (including touching endpoints) intervals and return the minimal set of non-overlapping intervals that cover them. Key pattern: sort by start and sweep/merge adjacent ranges whose starts are <= current end.

Asked at:

Google

Amazon

DESCRIPTION

Input:


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

Output:


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

Explanation: Intervals [1,3] and [2,6] overlap (2 <= 3), so they merge into [1,6]. The other intervals don't overlap with anything.

Constraints:

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start_i <= end_i <= 10^4
Intervals can be given in any order

Understanding the Problem

Let's understand what we're being asked to do. We have a list of intervals like [[1,3], [2,6], [8,10], [15,18]] where each interval is a pair [start, end].

Our goal is to merge overlapping intervals. Two intervals overlap if one starts before or exactly when the other ends. For example, [1,3] and [2,6] overlap because 2 <= 3, so they merge into [1,6]. Similarly, [1,3] and [3,5] are considered overlapping (touching endpoints count!) and merge into [1,5].

Tracing through the example: [1,3] and [2,6] overlap → merge to [1,6]. Then [8,10] doesn't overlap with [1,6] (gap between 6 and 8), so it stays separate. Finally [15,18] is also separate.

Key constraint: Intervals can be given in any order, not necessarily sorted!

Edge cases to consider: What if all intervals overlap into one big interval? What if no intervals overlap at all? What if we have just one interval? What about intervals like [1,4] and [4,5] where endpoints touch exactly?

Brute Force Approach

The brute force approach would check every pair of intervals to see if they overlap, repeatedly merging overlapping pairs until no more merges are possible. For each interval, we'd scan through all other intervals to find overlaps, merge them, and repeat this process until a full pass produces no merges. This approach is inefficient because it requires multiple passes through the data and doesn't take advantage of any ordering.

Building Intuition

If we process intervals in sorted order by start time, we can make a simple decision: does the current interval overlap with the previous merged interval?

Two intervals [a,b] and [c,d] overlap if c <= b (the second starts before or when the first ends). When they overlap, the merged interval is [a, max(b,d)].

By sorting first, we transform a complex problem (checking all pairs of intervals) into a single linear pass.

Once sorted, we only need to compare each interval with the most recent merged interval - we never need to look back at earlier intervals because they're guaranteed to be too far left to overlap.

Imagine scheduling meeting rooms. If you sort meetings by start time, you can process them in order:

Start with the first meeting as your 'current block'
For each new meeting, check: does it start before the current block ends?
If yes, extend the current block to include it (merge)
If no, the current block is complete - start a new block

This sweep line approach (moving left to right through sorted data) is a fundamental pattern for interval problems.

Common Mistakes

Forgetting to sort intervals first - the merge logic only works correctly on sorted data

Using < instead of <= when checking overlap - touching endpoints should be considered overlapping

Not updating the merged interval's end correctly - it should be max(currentEnd, newEnd), not just newEnd

Forgetting to add the last merged interval to the result after the loop completes

Modifying the input array in place without considering if that's allowed - some problems require preserving the original input

Optimal Solution

The optimal approach first sorts intervals by their start time, then makes a single pass through the sorted list. Maintain a 'current merged interval' starting with the first interval. For each subsequent interval, check if it overlaps with the current merged interval (current start <= current end). If it overlaps, extend the current interval's end to the maximum of both ends. If it doesn't overlap, add the current interval to the result and start a new current interval. This single-pass approach after sorting achieves optimal time complexity.

def merge_intervals(intervals):
    """
    Merge all overlapping intervals into minimal non-overlapping set.
    Sort by start time, then sweep through merging adjacent ranges.
    """
    # Handle empty input
    if not intervals:
        return []
    
    # Sort intervals by start time
    intervals.sort(key=lambda x: x[0])
    
    # Initialize result with first interval
    merged = [intervals[0]]
    
    # Sweep through sorted intervals
    for i in range(1, len(intervals)):
        current_interval = intervals[i]
        last_merged = merged[-1]
        
        # Check if current overlaps with last merged interval
        if current_interval[0] <= last_merged[1]:
            # Overlapping: extend the end of last merged interval
            last_merged[1] = max(last_merged[1], current_interval[1])
        else:
            # Non-overlapping: add current interval to result
            merged.append(current_interval)
    
    return merged

Start merge intervals algorithm

0 / 15

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log n) Sorting the intervals takes O(n log n) time, and the subsequent merge pass takes O(n) time. The sorting dominates, giving us O(n log n) overall

Space Complexity: O(n) We need O(n) space for the output array to store the merged intervals. The sorting may use O(log n) or O(n) space depending on the algorithm used

What We've Learned

Sort-then-sweep pattern: When dealing with interval problems, sorting by start time transforms a complex overlap detection problem into a simple linear scan - you only need to compare each interval with the previous merged one, not all intervals against each other.
Greedy merging strategy: Track the current merged interval's end boundary; if the next interval's start is ≤ current end, extend the end to max(current end, next end) - this greedy approach works because sorting guarantees no earlier interval can overlap with future ones.
Boundary condition precision: Intervals are overlapping when `next.start <= current.end` (not just `<`) because touching endpoints like [1,3] and [3,5] should merge into [1,5] - missing the equality is a common bug that leaves adjacent intervals unmerged.
In-place vs new array tradeoff: Building a new result array is cleaner than modifying the input in-place; the O(n) space cost is acceptable and avoids complex index manipulation when merging multiple consecutive intervals.
Time complexity insight: O(n log n) sorting dominates the O(n) merging pass, making this approach optimal for the general case - you cannot do better than O(n log n) without additional constraints because you must examine all interval relationships.
Calendar and scheduling applications: This pattern directly applies to meeting room scheduling, resource allocation, and time-slot booking systems where you need to find free slots or detect conflicts by consolidating occupied time ranges.

Test Your Understanding

Why is intervals the right data structure for this problem?

intervals provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid November, 2025

Google

Senior

Early October, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More