Start by sorting intervals by their start values to ensure sequential processing. Iterate through each interval and merge it with the previous one if they overlap. This approach guarantees a minimal set of non-overlapping intervals while maintaining linear scan efficiency after sorting, making it ideal for array plus sorting pattern problems.
Problem Statement
Given an array of intervals where each interval is represented as [starti, endi], merge all overlapping intervals and return an array of non-overlapping intervals that covers all original intervals. Intervals may touch or overlap, and the output should combine them to form the minimal number of ranges.
For example, given intervals = [[1,3],[2,6],[8,10],[15,18]], the result should be [[1,6],[8,10],[15,18]] because the first two intervals overlap. Another example: intervals = [[1,4],[4,5]] should return [[1,5]] as overlapping endpoints are merged.
Examples
Example 1
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Intervals [1,4] and [4,5] are considered overlapping.
Constraints
- 1 <= intervals.length <= 104
- intervals[i].length == 2
- 0 <= starti <= endi <= 104
Solution Approach
Sort intervals by start time
Begin by sorting the intervals based on their starting values. This ensures that any overlapping intervals are adjacent, simplifying the merging process.
Iterate and merge overlaps
Initialize an empty list for merged intervals. Traverse the sorted intervals, and if the current interval overlaps with the last interval in the merged list, update the end to the maximum end value. Otherwise, append it as a new interval.
Return consolidated intervals
After processing all intervals, return the merged list. This guarantees all overlapping ranges are combined and non-overlapping intervals remain in order.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Sorting takes O(n log n) and iterating to merge intervals is O(n), so the overall time complexity is O(n log n). Space complexity is O(n) in the worst case for storing merged intervals.
What Interviewers Usually Probe
- Checks if you sort intervals before merging, as failing to sort leads to incorrect merges.
- Looks for a clean in-place or linear pass after sorting, showing understanding of array traversal and comparison.
- Wants explanation of edge cases where intervals share endpoints or fully overlap.
Common Pitfalls or Variants
Common pitfalls
- Failing to sort intervals first, causing incorrect overlap detection.
- Not updating the end of merged intervals correctly, leading to incomplete merges.
- Ignoring cases where intervals touch but do not strictly overlap, e.g., [1,4] and [4,5].
Follow-up variants
- Merge intervals with additional interval insertion, testing dynamic updates to merged lists.
- Merge intervals using linked list structure instead of array, emphasizing pointer manipulation.
- Count overlapping intervals without merging, focusing on interval coverage rather than consolidation.
How GhostInterview Helps
- Highlights correct sorting and iteration patterns for array plus sorting problems.
- Identifies failure modes such as missed overlaps or unsorted input.
- Provides a step-by-step merge simulation with explanations for each interval comparison.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main idea behind the Merge Intervals problem?
Sort the intervals by start time and sequentially merge overlapping intervals to produce non-overlapping ranges.
Can intervals that touch at endpoints be merged?
Yes, intervals like [1,4] and [4,5] are considered overlapping for merging purposes.
What is the time complexity for the Merge Intervals solution?
Sorting takes O(n log n) and merging takes O(n), so the total is O(n log n).
How does the array plus sorting pattern apply here?
Sorting ensures overlaps are adjacent, and linear scanning merges intervals efficiently, showcasing array plus sorting pattern usage.
What common mistakes should I avoid when merging intervals?
Do not skip sorting, fail to update merged ends, or ignore intervals that only touch at endpoints.
Need direct help with Merge Intervals instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Merge Intervals from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Group the anagrams in a list of strings using efficient hash table-based methods, focusing on array scanning.
Open problem page#47 Permutations IIGenerate all unique permutations of an array containing duplicates using backtracking and pruning to avoid repeated sequences efficiently.
Open problem page#75 Sort ColorsSort Colors requires in-place reordering of an array using a two-pointer scanning strategy to group 0s, 1s, and 2s efficiently.
Open problem page