How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Find missing ranges in interval | Meta Coding Question

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.

Input: ([], 0, 99)

Expected Output: ['0->99']

Explanation: Empty nums means the entire interval [0,99] is one contiguous missing range.

Input: ([-1], -1, -1)

Expected Output: []

Explanation: The only integer in the interval, -1, is present in nums, so nothing is missing.

Input: ([-2147483648, 2147483647], -2147483648, 2147483647)

Expected Output: ['-2147483647->2147483646']

Explanation: Both 32-bit boundaries are covered; the gigantic middle range -2147483647..2147483646 is missing. Computing it via subtraction avoids integer overflow at the boundaries.

Input: ([0], -1, 0)

Expected Output: ['-1']

Explanation: 0 is covered; only -1 at the lower boundary is missing, formatted as a single number.

Input: ([5, 6, 7, 8, 9], 5, 9)

Expected Output: []

Explanation: Every integer in [5,9] appears in nums, so there are no missing ranges.

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.

Quick Overview

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.