Skip to main content

16. Merge Intervals

mediumAsked at Nubank

Merge a list of overlapping intervals into the minimum disjoint set; Nubank uses it as an analog for collapsing overlapping hold-amounts on a credit-card ledger.

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

Problem

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of non-overlapping intervals that cover the same ranges.

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 the list and merge any overlapping pair until no changes.

Time
O(n^2)
Space
O(n)
// repeat: for each pair (i,j) if overlap merge, restart scan; stop when no merges happen.

Tradeoff:

2. Sort then sweep

Sort by start, then walk once and extend the last merged interval when the next starts inside it.

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

Tradeoff:

Nubank-specific tips

Nubank likes when you mention that intervals could be hold windows on a credit-card authorization stream; ask whether updates arrive sorted from the rail or arbitrarily.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →