LeetCode 56 - Merge Intervals

LeetCode Problem 56

Difficulty: 🟡 Medium
Topics: Array, Sorting

Solution

Problem Understanding

The problem gives an array of intervals, where each interval is represented as [start, end]. Each interval describes a continuous range of values from start to end, inclusive.

The goal is to combine all intervals that overlap into a single larger interval. After merging all overlapping intervals, we return a list of intervals where no two intervals overlap anymore.

For example, if we have:

[1,3] and [2,6]

these intervals overlap because the second interval starts before the first one ends. Together, they cover the continuous range from 1 to 6, so they should be merged into:

[1,6]

The output must contain the minimum number of intervals needed to represent the same covered ranges as the original input.

A very important detail is that intervals touching at boundaries are also considered overlapping. For example:

[1,4] and [4,5]

must merge into:

[1,5]

because the end of the first interval equals the start of the second interval.

The constraints tell us that:

• There can be up to 10^4 intervals.
• Each interval contains exactly two integers.
• Interval values are relatively small, but the number of intervals is large enough that inefficient quadratic solutions may become slow.

This immediately suggests that we should look for an O(n log n) solution, which usually points toward sorting.

Several edge cases are important:

• Intervals may already be sorted.
• Intervals may be completely unsorted.
• One interval may fully contain another.
• Multiple intervals may chain together into one large interval.
• There may be only one interval.
• Intervals that only touch at endpoints must still merge correctly.

Approaches

Brute Force Approach

A straightforward idea is to repeatedly compare intervals against each other and merge any overlapping pairs.

One possible brute-force strategy works like this:

1. Compare every interval with every other interval.
2. If two intervals overlap, merge them.
3. Restart the process because the newly merged interval may overlap with additional intervals.
4. Continue until no more merges are possible.

This approach is correct because eventually every overlapping pair will be combined. However, it is inefficient because repeated scans are required after every merge.

In the worst case, each merge operation may require scanning the entire list again, leading to quadratic or even worse behavior depending on implementation details.

With up to 10^4 intervals, an O(n^2) approach becomes unnecessarily expensive.

Optimal Approach

The key observation is that overlapping intervals become much easier to process once the intervals are sorted by starting value.

After sorting:

• Any interval that overlaps with the current interval must appear immediately after it.
• Once we encounter a non-overlapping interval, we know no future interval can overlap with the current merged interval.

This transforms the problem into a single linear scan after sorting.

The algorithm becomes:

1. Sort intervals by start time.
2. Maintain a current merged interval.
3. For each next interval:

• If it overlaps, extend the current interval.
• Otherwise, save the current interval and start a new one.

Sorting is the critical step because it guarantees overlapping intervals appear consecutively.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) or O(n)	Repeatedly compare and merge intervals
Optimal	O(n log n)	O(n)	Sort intervals first, then merge in one pass

Algorithm Walkthrough

Optimal Algorithm

1. Sort all intervals by their starting value.

Sorting ensures that intervals are processed from left to right. Once sorted, any overlapping intervals must appear next to each other. 2. Initialize the result list.

This list will store the final merged intervals. 3. Start with the first interval as the current interval.

Since intervals are sorted, the first interval becomes the starting point for merging. 4. Iterate through the remaining intervals one by one.

For each interval, compare its start value with the end value of the current merged interval. 5. Check whether the intervals overlap.

Two intervals overlap if:

next_start <= current_end

This includes intervals that touch at boundaries. 6. If they overlap, merge them.

Update the current interval’s end value to:

max(current_end, next_end)

This expands the merged interval to cover both ranges. 7. If they do not overlap, finalize the current interval.

Add the current interval to the result list because no future interval can overlap with it after sorting. 8. Start a new current interval.

The non-overlapping interval becomes the new interval being tracked. 9. After the loop ends, append the final current interval.

The last merged interval has not yet been added to the result list.

Why it works

The algorithm works because sorting guarantees intervals are processed in increasing order of their start values. At any moment, the current merged interval represents the union of all overlapping intervals seen so far.

If the next interval starts before or at the current interval’s end, they must overlap and should be merged. If the next interval starts after the current interval’s end, then no later interval can overlap with the current interval because all later intervals start even farther to the right.

This invariant guarantees correctness.

Python Solution

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda interval: interval[0])

        merged = []

        current_start, current_end = intervals[0]

        for start, end in intervals[1:]:
            if start <= current_end:
                current_end = max(current_end, end)
            else:
                merged.append([current_start, current_end])
                current_start, current_end = start, end

        merged.append([current_start, current_end])

        return merged

The implementation starts by sorting intervals according to their starting values. This is the foundation of the algorithm because it guarantees overlapping intervals appear consecutively.

The merged list stores the final answer.

The variables current_start and current_end track the interval currently being merged. Initially, they are set to the first interval in the sorted array.

The loop processes each remaining interval:

• If the next interval overlaps with the current one, we extend current_end.
• Otherwise, the current interval is complete, so we append it to merged and begin tracking a new interval.

After the loop finishes, the final interval still needs to be added because it has not yet been appended inside the loop.

The method then returns the fully merged list.

Go Solution

package main

import "sort"

func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	merged := [][]int{}

	currentStart := intervals[0][0]
	currentEnd := intervals[0][1]

	for i := 1; i < len(intervals); i++ {
		start := intervals[i][0]
		end := intervals[i][1]

		if start <= currentEnd {
			if end > currentEnd {
				currentEnd = end
			}
		} else {
			merged = append(merged, []int{currentStart, currentEnd})

			currentStart = start
			currentEnd = end
		}
	}

	merged = append(merged, []int{currentStart, currentEnd})

	return merged
}

The Go implementation follows the same logic as the Python solution.

The main language-specific difference is sorting. In Go, we use sort.Slice with a custom comparator function.

Go slices are reference-like structures, so appending intervals directly into merged is efficient.

No special handling for integer overflow is needed because the interval values are small and safely fit within Go’s int type.

Worked Examples

Example 1

Input:

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

Step 1: Sort intervals

The intervals are already sorted:

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

Step 2: Initialize current interval

current = [1,3]
merged = []

Step 3: Process intervals

Next Interval	Overlaps?	Action	Current Interval	Merged
[2,6]	Yes	Merge	[1,6]	[]
[8,10]	No	Save current	[8,10]	[[1,6]]
[15,18]	No	Save current	[15,18]	[[1,6],[8,10]]

Step 4: Append final interval

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

Final output:

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

Example 2

Input:

[[1,4],[4,5]]

Step 1: Sort intervals

[[1,4],[4,5]]

Step 2: Initialize

current = [1,4]
merged = []

Step 3: Compare intervals

Next Interval	Overlaps?	Action	Current Interval
[4,5]	Yes	Merge	[1,5]

The intervals overlap because:

4 <= 4

Step 4: Append final interval

merged = [[1,5]]

Final output:

[[1,5]]

Example 3

Input:

[[4,7],[1,4]]

Step 1: Sort intervals

[[1,4],[4,7]]

Step 2: Initialize

current = [1,4]
merged = []

Step 3: Compare intervals

Next Interval	Overlaps?	Action	Current Interval
[4,7]	Yes	Merge	[1,7]

Step 4: Append final interval

merged = [[1,7]]

Final output:

[[1,7]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Output list may contain up to n intervals

The linear merge pass itself only takes O(n) time because each interval is processed exactly once. However, sorting requires O(n log n) time, which becomes the dominant cost.

The output array may store all intervals in the worst case when no intervals overlap, so the space complexity is O(n).

Test Cases

solution = Solution()

# Basic overlapping intervals
assert solution.merge([[1,3],[2,6],[8,10],[15,18]]) == [
    [1,6],[8,10],[15,18]
]

# Touching intervals should merge
assert solution.merge([[1,4],[4,5]]) == [
    [1,5]
]

# Unsorted input
assert solution.merge([[4,7],[1,4]]) == [
    [1,7]
]

# Single interval
assert solution.merge([[5,8]]) == [
    [5,8]
]

# No overlapping intervals
assert solution.merge([[1,2],[3,4],[5,6]]) == [
    [1,2],[3,4],[5,6]
]

# One interval completely contains others
assert solution.merge([[1,10],[2,3],[4,5],[6,7]]) == [
    [1,10]
]

# Multiple chained overlaps
assert solution.merge([[1,2],[2,3],[3,4],[4,5]]) == [
    [1,5]
]

# Duplicate intervals
assert solution.merge([[1,4],[1,4],[1,4]]) == [
    [1,4]
]

# Nested intervals
assert solution.merge([[1,5],[2,3]]) == [
    [1,5]
]

# Large gap between intervals
assert solution.merge([[1,2],[100,200]]) == [
    [1,2],[100,200]
]

# Mixed overlaps
assert solution.merge([[1,4],[0,2],[3,5]]) == [
    [0,5]
]

Test	Why
[[1,3],[2,6],[8,10],[15,18]]	Standard overlap example
[[1,4],[4,5]]	Verifies endpoint-touching merge
[[4,7],[1,4]]	Verifies sorting is required
[[5,8]]	Smallest valid input
[[1,2],[3,4],[5,6]]	No merges should occur
[[1,10],[2,3],[4,5],[6,7]]	One interval fully contains others
[[1,2],[2,3],[3,4],[4,5]]	Chain merging behavior
[[1,4],[1,4],[1,4]]	Duplicate intervals
[[1,5],[2,3]]	Nested interval handling
[[1,2],[100,200]]	Widely separated intervals
[[1,4],[0,2],[3,5]]	Multiple partial overlaps

Edge Cases

Intervals That Touch at Boundaries

A very common bug is treating intervals like [1,4] and [4,5] as non-overlapping. The problem explicitly states that touching intervals should merge.

The implementation handles this correctly using:

if start <= current_end:

The equality condition is essential. Using < instead of <= would produce incorrect results.

Completely Nested Intervals

Consider:

[[1,10],[2,3],[4,5]]

A buggy implementation might accidentally append smaller intervals separately.

The algorithm avoids this because when overlap occurs, it updates:

current_end = max(current_end, end)

Since 10 is already larger than all nested interval endpoints, the outer interval remains unchanged.

Unsorted Input

The input is not guaranteed to be sorted.

For example:

[[5,7],[1,3],[2,4]]

Without sorting first, the algorithm could incorrectly finalize intervals too early.

Sorting guarantees all potentially overlapping intervals appear consecutively, which is why the merge process works correctly with a single pass afterward.