Skip to main content

56. Merge Intervals

mediumAsked at Elastic

Merge all overlapping intervals into a minimal non-overlapping set. Elastic frequently asks this because merging time-range queries, log time spans, and APM trace windows are everyday operations in Elasticsearch and Kibana — getting the overlap condition exactly right under edge cases is a real engineering concern.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2026-Q1)— Elastic SWE candidates consistently report interval problems as part of mid-difficulty rounds, reflecting the time-series nature of Elastic's product.
  • Blind (2025-11)— Merge Intervals cited in Elastic interview threads as a question where interviewers probe edge cases around touching vs. overlapping intervals.

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: [1,3] and [2,6] overlap since 2 <= 3; merged to [1,6].

Example 2

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

Explanation: [1,4] and [4,5] are considered overlapping (touching counts).

Approaches

1. Sort by start, linear scan

Sort intervals by start time. Walk through sorted intervals: if the current interval's start <= the last merged interval's end, they overlap — update the merged end to the max of both ends. Otherwise, push the current interval as a new non-overlapping interval.

Time
O(n log n)
Space
O(n)
function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    if (intervals[i][0] <= last[1]) {
      // Overlap: extend the end if needed
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      merged.push(intervals[i]);
    }
  }
  return merged;
}

Tradeoff: O(n log n) dominated by sort; linear scan after. This is the standard solution — optimal for this problem.

Elastic-specific tips

Elastic interviewers probe two edge cases: (1) touching intervals [1,4],[4,5] — these overlap because start <= end (use <=, not <). (2) An interval completely contained inside another [1,10],[2,5] — use max(last.end, curr.end) not just curr.end to avoid shrinking the merged window. Connect to the real use case: 'In Kibana, when a user adjusts a time filter, overlapping query windows must be merged before sending to Elasticsearch to avoid redundant shard queries.'

Common mistakes

  • Using < instead of <= for the overlap condition — touching intervals like [1,4],[4,5] must be merged.
  • Updating merged end to curr.end instead of max(last.end, curr.end) — a contained interval would incorrectly shrink the window.
  • Not sorting before scanning — the algorithm assumes intervals are ordered by start time.
  • Starting the result array empty and special-casing the first interval — initialize with intervals[0] to simplify the loop.

Follow-up questions

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

  • Insert Interval (LC 57) — insert a new interval into a sorted non-overlapping list.
  • Non-overlapping Intervals (LC 435) — find the minimum number of intervals to remove to make the rest non-overlapping.
  • How would you merge intervals across 100 sorted shards in parallel?

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 time instead of end time?

Sorting by start time guarantees that if two intervals overlap, the one with the smaller start always appears first, making the linear scan correct with a single comparison per step.

What is the time complexity after the sort?

The scan is O(n) — each interval is visited exactly once. The overall complexity is O(n log n) due to the sort.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →