Skip to main content

52. Merge Intervals

mediumAsked at Snowflake

Merge overlapping intervals. Snowflake asks this to test sort-then-sweep — the same primitive used to coalesce overlapping micro-partition ranges during clustering maintenance.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake clustering-team uses this in onsites to anchor partition-coalesce discussion.
  • LeetCode Discuss (2025-12)— Recurring at Snowflake new-grad onsites.

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.

Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^4

Examples

Example 1

Input
intervals = [[1,3],[2,6],[8,10],[15,18]]
Output
[[1,6],[8,10],[15,18]]

Example 2

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

Approaches

1. Pairwise overlap check

Repeatedly scan for overlapping pairs and merge until no more changes.

Time
O(n^2) or worse
Space
O(n)
// Naive: while changed, find any overlapping pair and merge them.
// Worst case n^2. Don't ship.

Tradeoff: Quadratic or worse. Mention to reject.

2. Sort by start + linear sweep (optimal)

Sort by start. Iterate, maintaining a current 'open' merged interval. If next start <= current end, extend end; else push current and start new.

Time
O(n log n)
Space
O(n) output
function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [];
  for (const [s, e] of intervals) {
    if (result.length && result[result.length - 1][1] >= s) {
      result[result.length - 1][1] = Math.max(result[result.length - 1][1], e);
    } else {
      result.push([s, e]);
    }
  }
  return result;
}

Tradeoff: Sort dominates at n log n. Linear sweep is O(n). The shape of clustering compaction in their executor.

Snowflake-specific tips

Snowflake interviewers grade this on whether the sort step is explicitly justified ('sort by start lets us detect overlaps in one pass'). Bonus signal: connect to micro-partition clustering — when partitions overlap on the clustering key, auto-clustering picks up overlapping ranges via sort-then-sweep and merges them.

Common mistakes

  • Using > instead of >= for the overlap check — fails for touching intervals like [1,4] and [4,5].
  • Forgetting that the input may already be sorted (sort is idempotent but worth mentioning).
  • Sorting by end instead of start — fails when overlapping intervals have different starts.

Follow-up questions

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

  • Insert Interval (LC 57).
  • Meeting Rooms (LC 252).
  • How does Snowflake auto-cluster overlapping micro-partitions?

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 sort by start?

After sorting, any overlap can only happen between consecutive intervals (transitively). One pass suffices.

How does this connect to micro-partitions?

Each micro-partition stores [min, max] for its clustering key. When ingest creates overlapping ranges, auto-clustering detects them via sort-by-min then sweep, then writes merged partitions.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →