56. Merge Intervals

Q: Why must I sort first?

Without sorting, a later interval could merge with a much earlier one that you already pushed and stopped tracking. Sorting by start guarantees that if no overlap exists with the previous tail, no overlap exists with anything earlier.

Q: What if intervals can have duplicate starts?

The sort-then-sweep still works. The first one in (by sort order) becomes the tail; any duplicate-start later one will either be fully contained (no change to end) or extend the end (Math.max handles both).

mediumAsked at Robinhood

Given a list of intervals, merge overlapping ones. Robinhood asks this to test interval reasoning that maps directly to consolidating trade windows, market-data ticks, and scheduling jobs across overlapping price-feed batches.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

Glassdoor (2026-Q1)— Robinhood mid-level SWE onsite reports list Merge Intervals as a recurring 30-minute problem.
Levels.fyi (2025-12)— Robinhood SWE-II loop trip report cites Merge Intervals as the second coding round.

Problem

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.

Constraints

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

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 and merge into [1,6].

Example 2

Input

intervals = [[1,4],[4,5]]

Output

[[1,5]]

Explanation: Touching intervals are considered overlapping.

Approaches

1. Brute-force compare every pair

For each pair check overlap, merge, restart. Repeat until no merges happen.

Time: O(n^2)
Space: O(n)

function mergeBrute(intervals) {
  const result = intervals.map(i => i.slice());
  let merged = true;
  while (merged) {
    merged = false;
    for (let i = 0; i < result.length; i++) {
      for (let j = i + 1; j < result.length; j++) {
        if (result[i][1] >= result[j][0] && result[j][1] >= result[i][0]) {
          result[i] = [Math.min(result[i][0], result[j][0]), Math.max(result[i][1], result[j][1])];
          result.splice(j, 1);
          merged = true;
          break;
        }
      }
      if (merged) break;
    }
  }
  return result;
}

Tradeoff: Easy to think about but slow. Worth mentioning briefly before you pivot to the sort-then-sweep optimal.

2. Sort by start + linear sweep (optimal)

Sort by start time. Walk through and either extend the last merged interval or push a new one.

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

function merge(intervals) {
  if (intervals.length === 0) return [];
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [intervals[0].slice()];
  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    const [start, end] = intervals[i];
    if (start <= last[1]) {
      last[1] = Math.max(last[1], end);
    } else {
      result.push([start, end]);
    }
  }
  return result;
}

Tradeoff: O(n log n) is dominated by the sort. After sorting, a single linear pass is enough because any future interval that overlaps the current merged tail must start within its range.

Robinhood-specific tips

Robinhood interviewers care about whether touching intervals like [1,4] and [4,5] should merge. The default per the LeetCode constraint is YES — explicitly state your assumption and ask before coding. Also be careful with the in-place vs copy choice: mutating last[1] in the result array is the cleanest version; constructing new intervals in a loop is needlessly slower.

Common mistakes

Forgetting to sort first — the sweep only works on sorted input.
Using start < last[1] instead of start <= last[1], which fails on touching intervals.
Returning intervals.sort(...) directly when the sort comparator is wrong for numbers (default sort is lexicographic — '10' < '2').

Follow-up questions

An interviewer at Robinhood may pivot to one of these next:

Insert Interval — given a sorted non-overlapping list, insert a new one and merge.
Meeting Rooms II — minimum number of rooms (heap or sweepline).
Employee Free Time — given each employee's schedule, return common free intervals.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why must I sort first?

Without sorting, a later interval could merge with a much earlier one that you already pushed and stopped tracking. Sorting by start guarantees that if no overlap exists with the previous tail, no overlap exists with anything earlier.

What if intervals can have duplicate starts?

The sort-then-sweep still works. The first one in (by sort order) becomes the tail; any duplicate-start later one will either be fully contained (no change to end) or extend the end (Math.max handles both).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Merge Intervals and other Robinhood interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →