Merge Intervals LeetCode Solution: Sort, Sweep & Merge

If you could only study one interval problem before a coding interview, it should be Merge Intervals (#56). This problem appears on interview panels at Amazon, Google, Meta, Bloomberg, and virtually every company that asks algorithm questions. It is consistently ranked among the top five most frequently asked medium-difficulty problems on LeetCode.

Merge Intervals teaches you the sort-first pattern — a technique so fundamental that once you understand it, every other interval problem becomes a variation of the same idea. Problems like Insert Interval (#57), Non-overlapping Intervals (#435), and Meeting Rooms II (#253) all build directly on the approach you will learn here.

In this walkthrough, you will understand the problem from scratch, build the solution step by step, trace through a visual example, handle every edge case, and walk away with a reusable pattern for the entire interval category.

The problem statement is straightforward: given an array of intervals where each interval is a pair [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

For example, given [[1,3],[2,6],[8,10],[15,18]], the intervals [1,3] and [2,6] overlap because 2 falls within [1,3]. Merging them produces [1,6]. The intervals [8,10] and [15,18] do not overlap with anything else, so the final answer is [[1,6],[8,10],[15,18]].

Two intervals [a,b] and [c,d] overlap when one starts before the other ends. More precisely, they overlap if a <= d and c <= b. But you do not need to memorize that condition — the sort-first approach makes overlap detection trivially simple, as you will see in the next section.

The reason merge intervals leetcode trips people up is that intervals can arrive in any order. If you try to merge them without sorting, you need to compare every interval against every other interval — an O(n^2) approach that is both slow and complicated to implement correctly.

The breakthrough insight is simple: sort all intervals by their start time. Once sorted, overlapping intervals are guaranteed to be adjacent. You never need to look backwards or compare distant intervals. This single preprocessing step transforms a messy problem into a clean linear scan.

After sorting, the algorithm reduces to one pass through the array. For each interval, you check whether it overlaps with the last interval in your result. If it does, you extend the end of the last result interval. If it does not, you push the current interval as a new entry. That is the entire algorithm.

Let us build the merge intervals solution piece by piece. The approach works identically in Python, Java, JavaScript, and C++ — only the syntax changes. Here is the logic in plain steps.

First, handle the base case: if the input has zero or one interval, return it as-is since there is nothing to merge. Next, sort the intervals array by the start value of each interval. Initialize your result list with the first interval from the sorted array.

Now iterate through the remaining intervals starting from the second one. For each interval, compare its start value with the end value of the last interval in your result. If the current start is less than or equal to the last end, the intervals overlap — update the last end to be the maximum of both end values. Otherwise, the intervals do not overlap, so append the current interval to the result.

When the loop finishes, your result list contains all the merged intervals. The time complexity is O(n log n) for the sort plus O(n) for the merge pass, giving O(n log n) overall. The space complexity is O(n) for the output array, or O(log n) if you only count the sort stack space.

Let us trace through the classic example step by step. The input is [[1,3],[2,6],[8,10],[15,18]]. This array happens to already be sorted by start time, so we skip directly to the merge phase.

We initialize result with the first interval: result = [[1,3]]. Now we process [2,6]. The start value 2 is less than or equal to the last result end 3, so these intervals overlap. We update the last result end to max(3, 6) = 6. Result is now [[1,6]].

Next we process [8,10]. The start value 8 is greater than the last result end 6, so there is no overlap. We push [8,10] as a new interval. Result is now [[1,6],[8,10]].

Finally we process [15,18]. The start value 15 is greater than the last result end 10, so again no overlap. We push [15,18]. The final result is [[1,6],[8,10],[15,18]] — exactly the expected answer.

Notice how simple each decision is: one comparison, then either extend or push. The sort step did all the heavy lifting by guaranteeing that we only ever need to look at the last interval in our result.

The merge intervals algorithm handles edge cases gracefully, but you should be aware of the tricky ones that interviewers like to probe. A single interval in the input should return that interval unchanged. An input where every interval overlaps — like [[1,4],[2,5],[3,6]] — should produce a single merged interval [[1,6]]. An input where no intervals overlap should return the sorted input unchanged.

Touching intervals are the most commonly tested edge case. Given [1,2] and [2,3], should they merge into [1,3]? In LeetCode 56, yes — intervals that share an endpoint are considered overlapping. Our algorithm handles this correctly because we check current start <= last end, and 2 <= 2 is true. However, some problem variants define overlap strictly as current start < last end, so always read the constraints.

Once you have mastered Merge Intervals, you are prepared for the entire interval category. Insert Interval (#57) is the same pattern with one extra interval to insert before merging. Non-overlapping Intervals (#435) asks you to find the minimum number of intervals to remove — the sort-first greedy approach applies directly. Meeting Rooms II (#253) uses the same sorted intervals but tracks a heap of end times to count overlapping meetings.

Merge Intervals is not just a standalone problem — it is the foundation of an entire problem-solving pattern. The sort-then-sweep technique works the same way across all interval problems: sort by start time, then make a single pass with a simple decision at each step.

This pattern extends beyond LeetCode. In real-world software engineering, you will encounter interval merging when consolidating time ranges in calendars, merging overlapping IP address ranges, compacting database key ranges, and scheduling non-conflicting events. The same O(n log n) sort-then-sweep approach applies every time.

If you are preparing for coding interviews, add Merge Intervals to your must-review list. Practice it until the pattern is automatic — sort, initialize, iterate, extend or push. With YeetCode flashcards, you can drill the interval pattern alongside related problems so the technique stays fresh when interview day arrives.