Find missing ranges in interval
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a sorted unique integer array nums and two integers lower and upper defining an inclusive interval [lower, upper], return all missing ranges not present in nums within this interval. Format each missing range as "a" for single numbers or "a->b" for ranges. Consider cases where nums is empty, elements fall outside [lower, upper], or boundaries approach 32-bit integer limits. Aim for O(n) time and O(
1) extra space (excluding output).
Quick Answer: This question evaluates a candidate's proficiency in array traversal, interval reasoning, handling edge cases including empty inputs and 32-bit integer boundary conditions, and enforcing time and space complexity constraints.
Given a sorted unique integer array `nums` and two integers `lower` and `upper` defining an inclusive interval `[lower, upper]`, return a list of all the missing ranges — the maximal subranges of `[lower, upper]` whose every integer is absent from `nums`.
Format each missing range as a string:
- `"a"` if the range is a single number `a`.
- `"a->b"` if the range spans more than one number, from `a` to `b` inclusive.
Return the ranges in ascending order. Every element of `nums` lies within `[lower, upper]`, `nums` is sorted in strictly increasing order (no duplicates), and the values may approach 32-bit signed integer limits, so be careful not to overflow when checking adjacency.
Return an empty list if every integer in `[lower, upper]` is present in `nums`.
Constraints
- -2^31 <= lower <= upper <= 2^31 - 1
- 0 <= nums.length <= 100
- lower <= nums[i] <= upper for every i
- nums is sorted in strictly increasing order (all elements unique)
Examples
Input: ([0, 1, 3, 50, 75], 0, 99)
Expected Output: ['2', '4->49', '51->74', '76->99']
Explanation: Within [0,99]: 2 is missing (single), 4..49 missing, 51..74 missing, and 76..99 missing up to the upper bound.
Input: ([], 1, 1)
Expected Output: ['1']
Explanation: nums is empty and the interval [1,1] is a single integer, so the whole interval is one missing single-number range.
Hints
- Walk through the gaps between consecutive 'covered' points. Seed a `prev` value at `lower - 1` so the first real gap is measured from the left boundary, and treat `upper + 1` as a virtual element after the last real one so the final gap up to `upper` is captured.
- A missing range exists between two adjacent covered values `prev` and `cur` exactly when there is at least one integer strictly between them — i.e. when `cur - prev >= 2`. The missing range is then `[prev + 1, cur - 1]`.
- To avoid 32-bit overflow at INT_MIN / INT_MAX, compare the gap with subtraction (`cur - prev >= 2`) rather than computing `prev + 1` or `cur + 1` before you know a gap exists, and only form the boundary values once you've confirmed the gap.