Find gaps between intervals

Quick Overview

This question evaluates interval manipulation and range-coverage reasoning, testing skills in sorting, merging overlapping ranges, and handling boundary conditions within the Coding & Algorithms domain.

Find gaps between intervals

Company: Nuro

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of integer intervals `intervals`, where each interval is represented as `[start, end]` (inclusive), and `start <= end`. Two intervals may overlap or touch (e.g., `[1,3]` and `[4,6]` touch if you consider integers, because there is no missing integer between 3 and 4). Your task is to find **all gaps** (missing ranges) **between** the covered portions of the number line. More precisely: 1. Consider the union of all intervals. 2. Let `minCovered` be the smallest integer covered by any interval, and `maxCovered` be the largest integer covered by any interval. 3. Return a list of **all maximal missing integer ranges** within `[minCovered, maxCovered]` that are **not covered** by the union. Return the gaps as a list of disjoint intervals `[gapStart, gapEnd]` (inclusive), sorted by `gapStart`. ### Example - Input: `[[1,3],[7,10],[2,4]]` - Covered union is `[1,4] ∪ [7,10]` - Gaps within `[1,10]` are `[[5,6]]` - Output: `[[5,6]]` ### Notes / Edge cases - If the union is already contiguous (no gaps), return `[]`. - Overlapping intervals should not create gaps. - Intervals may be unsorted. ### Constraints (reasonable interview assumptions) - `1 <= len(intervals) <= 2e5` - Interval endpoints fit in 32-bit signed integers.

Quick Answer: This question evaluates interval manipulation and range-coverage reasoning, testing skills in sorting, merging overlapping ranges, and handling boundary conditions within the Coding & Algorithms domain.

|Home/Coding & Algorithms/Nuro
Nuro logo
Nuro
Nov 9, 2025
mediumSoftware EngineerTechnical ScreenCoding & Algorithms
15
0

You are given a list of integer intervals intervals, where each interval is represented as [start, end] (inclusive), and start <= end.

Two intervals may overlap or touch (e.g., [1,3] and [4,6] touch if you consider integers, because there is no missing integer between 3 and 4). Your task is to find all gaps (missing ranges) between the covered portions of the number line.

More precisely:

  1. Consider the union of all intervals.
  2. Let minCovered be the smallest integer covered by any interval, and maxCovered be the largest integer covered by any interval.
  3. Return a list of all maximal missing integer ranges within [minCovered, maxCovered] that are not covered by the union.

Return the gaps as a list of disjoint intervals [gapStart, gapEnd] (inclusive), sorted by gapStart.

Example

  • Input: [[1,3],[7,10],[2,4]]
    • Covered union is [1,4] ∪ [7,10]
    • Gaps within [1,10] are [[5,6]]
  • Output: [[5,6]]

Notes / Edge cases

  • If the union is already contiguous (no gaps), return [] .
  • Overlapping intervals should not create gaps.
  • Intervals may be unsorted.

Constraints (reasonable interview assumptions)

  • 1 <= len(intervals) <= 2e5
  • Interval endpoints fit in 32-bit signed integers.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...