Merge Intervals

medium
IntervalsArrayIntervalSorting

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

Examples

Example 1

  • 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, so they are merged into [1,6].

Example 2

  • Input: intervals = [[1,4],[4,5]]
  • Output: [[1,5]]
  • Explanation: Intervals [1,4] and [4,5] are considered overlapping since they share the endpoint 4.

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Sort and Merge

Intuition

The key insight is that once we sort the intervals by their start time, overlapping intervals will be adjacent. We iterate through the sorted intervals and compare each interval with the last interval in our result list. If they overlap (current start <= previous end), we merge them by extending the previous interval's end to the maximum of both ends. If they don't overlap, we start a new interval. This greedy approach works because sorting ensures we process intervals in order and never need to look back more than one step.

Algorithm

  1. Sort the intervals by their start time.
  2. Initialize a result list with the first interval.
  3. For each subsequent interval, compare it with the last interval in the result.
  4. If the current interval's start is less than or equal to the last result interval's end, they overlap. Update the last result interval's end to the maximum of both ends.
  5. Otherwise, add the current interval as a new entry in the result.
  6. Return the result list.
TimeO(n log n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> result;

        for (auto& interval : intervals) {
            if (result.empty() || result.back()[1] < interval[0]) {
                result.push_back(interval);
            } else {
                result.back()[1] = max(result.back()[1], interval[1]);
            }
        }

        return result;
    }
};
Java 21
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> result = new ArrayList<>();

        for (int[] interval : intervals) {
            if (result.isEmpty() || result.get(result.size() - 1)[1] < interval[0]) {
                result.add(interval);
            } else {
                result.get(result.size() - 1)[1] = Math.max(
                    result.get(result.size() - 1)[1], interval[1]
                );
            }
        }

        return result.toArray(new int[result.size()][]);
    }
}
Python 3.12
def merge(intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort()
    result = []

    for interval in intervals:
        if not result or result[-1][1] < interval[0]:
            result.append(interval)
        else:
            result[-1][1] = max(result[-1][1], interval[1])

    return result
Go 1.26
import "sort"

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

    result := [][]int{}

    for _, interval := range intervals {
        if len(result) == 0 || result[len(result)-1][1] < interval[0] {
            result = append(result, interval)
        } else {
            if interval[1] > result[len(result)-1][1] {
                result[len(result)-1][1] = interval[1]
            }
        }
    }

    return result
}
Approach 2

Connected Components (Graph-Based)

Intuition

We can model the problem as a graph where each interval is a node, and an edge exists between two nodes if their intervals overlap. Overlapping intervals form connected components, and each component should be merged into a single interval. We build an adjacency list by checking all pairs for overlap, then use BFS or DFS to find connected components. For each component, the merged interval is [min of all starts, max of all ends]. While less efficient than sorting, this approach offers a different perspective on the problem.

Algorithm

  1. Build an adjacency list: for each pair of intervals, add an edge if they overlap (one's start <= the other's end and vice versa).
  2. Use BFS or DFS to find all connected components.
  3. For each connected component, compute the merged interval as `[min(starts), max(ends)]`.
  4. Return the list of merged intervals.
TimeO(n^2)SpaceO(n^2)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<vector<int>> graph(n);

        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[i].push_back(j);
                    graph[j].push_back(i);
                }
            }
        }

        vector<bool> visited(n, false);
        vector<vector<int>> result;

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            queue<int> q;
            q.push(i);
            visited[i] = true;
            int lo = intervals[i][0], hi = intervals[i][1];

            while (!q.empty()) {
                int node = q.front(); q.pop();
                lo = min(lo, intervals[node][0]);
                hi = max(hi, intervals[node][1]);
                for (int neighbor : graph[node]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        q.push(neighbor);
                    }
                }
            }
            result.push_back({lo, hi});
        }

        return result;
    }
};
Java 21
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;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            visited[i] = true;
            int lo = intervals[i][0], hi = intervals[i][1];

            while (!queue.isEmpty()) {
                int node = queue.poll();
                lo = Math.min(lo, intervals[node][0]);
                hi = Math.max(hi, intervals[node][1]);
                for (int neighbor : graph.get(node)) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.offer(neighbor);
                    }
                }
            }
            result.add(new int[]{lo, hi});
        }

        return result.toArray(new int[result.size()][]);
    }
}
Python 3.12
from collections import deque

def merge(intervals: List[List[int]]) -> List[List[int]]:
    n = len(intervals)
    graph = [[] for _ in range(n)]

    for i in range(n):
        for j in range(i + 1, n):
            if intervals[i][0] <= intervals[j][1] and intervals[j][0] <= intervals[i][1]:
                graph[i].append(j)
                graph[j].append(i)

    visited = [False] * n
    result = []

    for i in range(n):
        if visited[i]:
            continue
        queue = deque([i])
        visited[i] = True
        lo, hi = intervals[i]

        while queue:
            node = queue.popleft()
            lo = min(lo, intervals[node][0])
            hi = max(hi, intervals[node][1])
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)

        result.append([lo, hi])

    return result
Go 1.26
func merge(intervals [][]int) [][]int {
    n := len(intervals)
    graph := make([][]int, n)
    for i := range graph {
        graph[i] = []int{}
    }

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if intervals[i][0] <= intervals[j][1] && intervals[j][0] <= intervals[i][1] {
                graph[i] = append(graph[i], j)
                graph[j] = append(graph[j], i)
            }
        }
    }

    visited := make([]bool, n)
    var result [][]int

    for i := 0; i < n; i++ {
        if visited[i] {
            continue
        }
        queue := []int{i}
        visited[i] = true
        lo, hi := intervals[i][0], intervals[i][1]

        for len(queue) > 0 {
            node := queue[0]
            queue = queue[1:]
            if intervals[node][0] < lo {
                lo = intervals[node][0]
            }
            if intervals[node][1] > hi {
                hi = intervals[node][1]
            }
            for _, neighbor := range graph[node] {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, neighbor)
                }
            }
        }
        result = append(result, []int{lo, hi})
    }

    return result
}

Frequently asked questions

What is the optimal time complexity of Merge Intervals?

The most efficient approach in this guide ("Connected Components (Graph-Based)") runs in O(n^2) time and uses O(n^2) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Merge Intervals use?

Merge Intervals is a medium-level Intervals problem involving Array, Interval, Sorting. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Merge Intervals be solved without extra space?

The most space-efficient approach in this guide uses O(n^2) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n), while the optimized version uses O(n^2).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
intervals=
[[1,3],[2,6],[8,10],[15,18]]
Expected Output
[[1,6],[8,10],[15,18]]