Skip to main content
Talentd

Merge Intervals - Solution & Explanation

MediumArraySorting20 min readAsked at: Amazon, Microsoft, Apple +109
Practice this problem

Problem Statement

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

 

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

 

Constraints:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

Approach Overview

Problem Overview: You receive a list of intervals where each interval represents a start and end time. Some intervals overlap. Your task is to merge all overlapping intervals and return a list of non‑overlapping intervals that cover the same ranges.

Approach 1: Sort and Merge Intervals (Time: O(n log n), Space: O(n))

The standard solution sorts intervals by their starting value, then performs a single linear scan to merge overlaps. Sorting ensures that if two intervals overlap, they appear next to each other. Start with the first interval and treat it as the current merged range. As you iterate through the sorted list, compare the current interval's start with the previous merged interval's end.

If the intervals overlap (current.start <= last.end), update the merged interval's end using max(last.end, current.end). If they do not overlap, push the previous interval into the result and start a new merged interval. This produces the minimal set of merged ranges in one pass after sorting. The algorithm relies on sorting followed by sequential processing of an array. Time complexity is O(n log n) due to sorting, while the merge scan itself is O(n). Space complexity is O(n) for the output list.

Approach 2: Interval Insertion Method (Time: O(n log n), Space: O(n))

This method treats the problem similarly to repeatedly inserting intervals into a merged result set. First sort the intervals by start time. Then iterate through them while maintaining a result list of non‑overlapping intervals. For each new interval, check whether it overlaps with the last interval already stored.

If there is no overlap (interval.start > result[-1].end), append it directly to the result. If an overlap exists, merge by expanding the end of the previous interval: result[-1].end = max(result[-1].end, interval.end). Conceptually, this approach views merging as incremental interval insertion into a maintained structure.

The advantage is conceptual clarity: the result array always stays valid and merged. The algorithm still requires sorting first, so the overall complexity remains O(n log n) time with O(n) space. The iteration step itself is linear.

Recommended for interviews: Interviewers typically expect the Sort and Merge approach. It demonstrates knowledge of sorting combined with linear scanning and interval reasoning. Explaining the overlap condition and why sorting guarantees adjacent overlaps shows strong problem‑solving skills. A brute force pairwise comparison would work but leads to O(n^2) complexity and signals weaker optimization awareness.

Approach 1: Sort and Merge Intervals

The key to solving this problem is to first sort the intervals based on the starting time. Once sorted, we can iterate over the intervals and merge them if they overlap. Two intervals overlap if the start of the current interval is less than or equal to the end of the previous interval.

In C, sorting is performed using qsort, with a custom comparator function. We iterate through each interval and merge overlapping intervals into a single one, storing the results in a new 2D array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), required for the output array.

Try this approach in the editor →

Approach 2: Interval Insertion Method

Another approach involves consecutive comparisons and inserting intervals into a new list if they do not overlap with the current interval being processed.

This method involves sorting first and directly inserting into the result list, verifying overlap in consecutive intervals.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n).
Space Complexity: O(n).

Try this approach in the editor →

Approach 3: Sorting + One-pass Traversal

We can sort the intervals in ascending order by the left endpoint, and then traverse the intervals for merging operations.

The specific merging operation is as follows.

First, we add the first interval to the answer. Then, we consider each subsequent interval in turn:

  • If the right endpoint of the last interval in the answer array is less than the left endpoint of the current interval, it means that the two intervals will not overlap, so we can directly add the current interval to the end of the answer array;
  • Otherwise, it means that the two intervals overlap. We need to use the right endpoint of the current interval to update the right endpoint of the last interval in the answer array, setting it to the larger of the two.

Finally, we return the answer array.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of intervals.

Code

PythonJavaC++GoTypeScriptRustC#Kotlin

Python

Java

C++

Go

TypeScript

Rust

C#

Kotlin

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sort and Merge Intervals

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), required for the output array.

Interval Insertion Method

Time Complexity: O(n log n).
Space Complexity: O(n).

Sorting + One-pass Traversal—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort and Merge IntervalsO(n log n)O(n)General case where intervals are unsorted. Most common and interview‑expected solution.
Interval Insertion MethodO(n log n)O(n)When building a merged result incrementally while iterating through sorted intervals.

Video Solution

Merge Overlapping Intervals | Brute, Optimal with Precise TC analysis • take U forward • 470,479 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Merge Intervals easy or hard?
Merge Intervals is considered a medium‑difficulty problem. The challenge comes from recognizing that sorting simplifies overlap detection and reduces the problem to a linear merge scan.
Merge Intervals Python/Java solution
Most implementations follow the same structure: sort intervals by start value, iterate through them, and merge overlaps by updating the previous interval's end. This logic translates directly across Python, Java, C++, C#, and JavaScript with only syntax differences.
How to solve Merge Intervals in O(n)?
O(n) time is possible only if the intervals are already sorted by start time. In that case, you simply iterate through the list once and merge overlapping intervals by comparing the current start with the previous end. Without sorted input, sorting is required, which increases complexity to O(n log n).
What is the best approach for Merge Intervals?
The best approach sorts the intervals by start time and then performs a single linear pass to merge overlaps. During the scan, compare each interval with the last merged interval and extend the end if they overlap. This solution runs in O(n log n) time due to sorting and O(n) space for the output list.
Is Merge Intervals asked at Google/Amazon/Meta?
Merge Intervals is a common interview problem at major tech companies including Google, Amazon, Meta, and Microsoft. It tests sorting, interval reasoning, and edge‑case handling. Variations of the problem often appear in system design or scheduling related questions.
What data structure is used in Merge Intervals?
The problem primarily uses arrays or lists to store intervals and results. Sorting algorithms organize the intervals by start time, and a dynamic result list keeps track of merged intervals during iteration.
What is the time complexity of Merge Intervals?
The optimal solution runs in O(n log n) time because the intervals must be sorted by their starting value. After sorting, the merge step requires only one linear scan, which is O(n). Space complexity is typically O(n) to store the merged intervals.

Ready to solve this problem?

Practice Merge Intervals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Bold Tag in String

Next

Amount of New Area Painted Each Day