161. Missing Ranges
You are given an inclusive interval [lower, upper] and a sorted array nums of distinct integers, all of which lie inside that interval. A number is missing if it is in [lower, upper] but not in nums.
Your answer describes the gaps nums leaves behind: sweep [lower, upper] in increasing order and report each maximal stretch of consecutive missing numbers as a single range, so every missing number lands in exactly one entry and no two entries could be merged into one. Format a range as "a->b" when a < b, or just "a" when it is a single number. If nothing is missing, return an empty list.
nums may be empty, in which case the whole interval is missing.
Example 1:
Input: lower = 0, upper = 9, nums = [0, 1, 3, 7]
Output: ["2", "4->6", "8->9"]
Explanation: Inside [0, 9] the numbers 2, 4, 5, 6, 8, 9 are absent from nums. Grouped into maximal runs they are 2 alone, 4 through 6, and 8 through 9.
Example 2:
Input: lower = 1, upper = 1, nums = []
Output: ["1"]
Explanation: nums is empty, so the single number in the interval is missing.
Constraints:
- -10⁹ ≤ lower ≤ upper ≤ 10⁹
- 0 ≤ nums.length ≤ 10⁴
- lower ≤ nums[i] ≤ upper
- nums is sorted in strictly increasing order (all values distinct).
Hints:
You never need to look at individual missing numbers — only at the gaps between consecutive covered numbers.
Keep a cursor `next` for the smallest number not yet accounted for, starting at lower. Each value x in nums either equals the cursor (no gap) or leaves the missing run [next, x - 1] behind; either way the cursor jumps to x + 1.
Append a sentinel value of upper + 1 after nums — it closes the final gap with no special-case code for the tail.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: lower = 0, upper = 9, nums = [0, 1, 3, 7]
Expected output: ["2", "4->6", "8->9"]