📖 8 min read
Last updated on

Merge Intervals — Coding Interview Walkthrough

By intervu.dev

Hero Image for Merge Intervals

You’re in a coding interview. The interviewer says: “Given a list of intervals, merge all the overlapping ones.” You’ve seen Merge Intervals before. You know sorting is involved. But now you need to explain your thinking out loud, handle edge cases on the fly, and write clean code while someone watches. That’s a very different challenge.

This walkthrough covers how that conversation unfolds: the clarifying questions that set you apart, the brute-force-to-optimal progression interviewers want to see, and the common traps that catch even prepared candidates.

The Problem

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. (LeetCode #56)

Example

Input

intervals = [[1,3],[2,6],[8,10],[15,18], "medium"]

Output

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

Explanation: Intervals [1,3] and [2,6] overlap because 2 falls within [1,3]. They merge into [1,6]. The remaining intervals don’t overlap with each other or with [1,6], so they stay as-is.

Already comfortable with the solution? Practice it in a mock interview →

Interval timeline with before row showing [1,3] and [2,6] overlapping plus [8,10] and [15,18] separate, and after row showing merged result [1,6], [8,10], [15,18].

What Interviewers Are Actually Testing

This problem is deceptively rich. A candidate who breezes through it quickly may miss edge cases. A candidate who thinks out loud and asks smart questions will stand out.

SkillWhat Interviewers Observe
Problem decompositionCan the candidate break this into smaller, manageable steps?
Sorting intuitionDo they recognize that sorting unlocks a cleaner solution?
Edge case awarenessDo they consider empty input, single intervals, or fully nested intervals?
Greedy reasoningCan they explain why a greedy approach works here?
Code clarityIs the implementation readable and interview-friendly?
CommunicationDo they think out loud and explain decisions as they code?

Step 1 — Clarifying Questions

Before writing a single line of code, strong candidates take a moment to clarify the problem. Here are smart questions to ask:

  • Are the intervals guaranteed to be sorted? The problem doesn’t specify, and sorting changes your approach significantly.
  • Can the input array be empty? You’ll want to handle intervals = [] gracefully.
  • Can intervals have equal start and end points (zero-length intervals)? For example, [3,3].
  • Are the interval values always integers? Floating-point edge cases are rare but worth confirming.
  • Can a single interval fully contain another? For example, [1,10] and [2,5] — should this merge into [1,10]? (Yes, but confirming shows thoroughness.)

Asking these questions serves two purposes: it helps you write a more robust solution, and it signals to the interviewer that you think like a professional engineer who considers real-world edge cases.

Step 2 — A First (Non-Optimal) Idea

A candidate might initially reach for a brute-force approach: compare every interval with every other interval and merge them if they overlap.

The naive approach would look something like:

  • For each interval, iterate over all other intervals.
  • If two intervals overlap (i.e., one’s start is within the other’s range), merge them into a new interval.
  • Repeat until no more merges are possible.

Why this is inefficient:

This approach involves repeated passes over the array. In the worst case — where intervals are heavily overlapping — the number of merge operations grows quickly, and you may need many passes before the array stabilizes.

ApproachTime Complexity
Brute force (nested loops, multiple passes)O(n²) or worse

This isn’t acceptable for large inputs. You want to do better.

Step 3 — The Key Insight

The core insight is straightforward:

If you sort the intervals by their start time, you only ever need to compare each interval to the one immediately before it.

Why does this work? After sorting, if two intervals overlap, they will be adjacent in the sorted array. There’s no way for interval A and interval C to overlap without interval B (which sits between them after sorting) also overlapping with one of them.

This means a single left-to-right pass is sufficient. You keep a “current” merged interval and check whether the next interval extends it or starts a fresh one.

In an interview, you’d explain this to your interviewer like so:

“Once I sort by start time, any interval that overlaps with the current one must have a start time within my current range. So I just track where my current merged interval ends, and if the next interval starts at or before that point, I extend it. Otherwise, I push the current interval to my result and start fresh.”

Step 4 — Optimal Strategy

  1. Handle edge case: If the input is empty, return an empty array immediately.
  2. Sort the intervals array by each interval’s start value in ascending order.
  3. Initialize a result list with the first interval as the starting “current” interval.
  4. Iterate through the remaining intervals one by one.
  5. For each interval, compare its start to the end of the last interval in the result:
    • If current_start <= last_end: the intervals overlap. Update the end of the last result interval to max(last_end, current_end) to handle fully-nested cases.
    • Otherwise: no overlap. Append the current interval to the result as a new entry.
  6. Return the result list.

Python Implementation

from typing import List

def merge(intervals: List[List[int]]) -> List[List[int]]:
    if not intervals:
        return [, "medium"]

    # Sort intervals by start time
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0], "medium"]

    for current in intervals[1:]:
        last = merged[-1, "medium"]

        # Intervals overlap if current start <= last end
        if current[0] <= last[1]:
            # Extend the last interval's end if needed
            last[1] = max(last[1], current[1])
        else:
            # No overlap — start a new interval
            merged.append(current)

    return merged

Why this is interview-friendly:

  • Variable names (last, current, merged) are descriptive and self-documenting.
  • The logic is a flat loop with no nested loops, making it easy to trace.
  • The max(last[1], current[1]) handles the fully-nested case (e.g., [1,10] containing [2,5]) cleanly without a separate branch.

Time Complexity

OperationComplexity
Sorting the intervalsO(n log n)
Single pass through the arrayO(n)
OverallO(n log n)
Space (result array)O(n)

The dominant cost is sorting. The merge pass itself is linear. This is optimal because you can’t do better than O(n log n) when you have to inspect all n intervals.

Common Interview Mistakes

  • Coding too early. Jumping straight to implementation without sorting or thinking through the approach leads to messy, hard-to-fix solutions mid-interview.
  • Forgetting to sort. This is the most common mistake. Without sorting, the greedy pass doesn’t work.
  • Missing the nested interval case. Using last[1] = current[1] instead of last[1] = max(last[1], current[1]) will fail on inputs like [[1,10],[2,5]].
  • Modifying the input array without checking. Some interviewers will ask whether it’s acceptable to sort in place. Clarify first.
  • Not explaining the greedy reasoning. Arriving at the right code without explaining why it works is a missed opportunity to demonstrate depth.
  • Skipping the empty input check. Always handle the edge case where intervals = [].

What a Strong Candidate Sounds Like

Here’s the kind of verbal explanation that impresses interviewers:

“My first instinct is to sort the intervals by start time. Once sorted, I know that if two intervals overlap, they’ll be right next to each other, so I only need a single pass. I’ll keep track of the last interval I’ve committed to, and for each new interval, I check if it starts before or at the end of that last one. If it does, I merge by extending the end. If not, I push the current one into my results and move on. The tricky case is when one interval is fully inside another, but taking the max of the two ends handles that cleanly.”

This explanation is clear, structured, and shows the candidate understands why the algorithm works, not just what it does.

Example Interview Dialogue

Interviewer: Given a list of intervals, merge all overlapping ones. What’s your approach?

Candidate: Can I ask a quick question first: is the input sorted by start time, or should I assume it’s unordered?

Interviewer: Assume it’s unordered.

Candidate: Got it. My first move then is to sort by start time. That’s the key. Once sorted, any two overlapping intervals will be adjacent, so I can do a single linear pass. I’ll initialize a result list with the first interval and then iterate through the rest. For each interval, if its start is less than or equal to the end of the last result interval, I merge by taking the max of the two endpoints. Otherwise, I push it as a new entry.

Interviewer: What’s your time complexity?

Candidate: O(n log n) for sorting, O(n) for the pass, so O(n log n) overall. Space is O(n) for the output.

Interviewer: What if two intervals share an endpoint — say [1,3] and [3,5]?

Candidate: Good edge case. Since 3 <= 3, my condition current[0] <= last[1] catches that and merges them into [1,5]. That matches the expected behavior.

Once you’re comfortable with the Merge Intervals explanation and solution, challenge yourself with these problems in the same “intervals” pattern category:

  • Insert Interval (LeetCode 57). Insert a new interval into a sorted, non-overlapping list and merge as needed.
  • Non-overlapping Intervals (LeetCode 435). Find the minimum number of intervals to remove to make the rest non-overlapping.
  • Meeting Rooms (LeetCode 252). Determine if a person can attend all meetings given a list of time intervals.
  • Meeting Rooms II (LeetCode 253). Find the minimum number of meeting rooms required.
  • Employee Free Time (LeetCode 759). Find the common free time across all employees’ schedules.

These problems share the same core intuition: sort by start time, then reason greedily about overlaps.

Practice This in a Mock Interview

Reading through a Merge Intervals explanation is a great start, but it’s very different from solving it live, under pressure, while talking through your reasoning out loud.

In a real interview, you won’t have a blog post in front of you. You’ll need to recall the sorting insight on the spot, handle follow-up questions, write clean code while explaining your choices, and catch your own edge cases in real time. That’s a skill you build through practice.

Start a mock interview for Merge Intervals on Intervu and practice with a realistic AI interviewer that gives instant feedback on your approach.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →