Missing Ranges

easy array

Problem

Given a sorted unique integer array nums and inclusive range [lower, upper], return the smallest sorted list of inclusive ranges [a, b] that cover exactly the missing numbers — those in [lower, upper] that are not in nums.

Inputnums = [0, 1, 3, 50, 75], lower = 0, upper = 99

Output[[2, 2], [4, 49], [51, 74], [76, 99]]

Compare consecutive values (with prev = lower-1, sentinel upper+1 at the end) and emit each gap.

nums (sorted, comma-separated)

lower

upper

def find_missing_ranges(nums, lower, upper):
    res = []
    prev = lower - 1
    for i in range(len(nums) + 1):
        cur = nums[i] if i < len(nums) else upper + 1
        if cur - prev >= 2:
            res.append([prev + 1, cur - 1])
        prev = cur
    return res

function findMissingRanges(nums, lower, upper) {
  const res = [];
  let prev = lower - 1;
  for (let i = 0; i <= nums.length; i++) {
    const cur = i < nums.length ? nums[i] : upper + 1;
    if (cur - prev >= 2) {
      res.push([prev + 1, cur - 1]);
    }
    prev = cur;
  }
  return res;
}

class Solution {
    public List<List<Integer>> findMissingRanges(int[] nums, int lower, int upper) {
        List<List<Integer>> res = new ArrayList<>();
        long prev = (long) lower - 1;
        for (int i = 0; i <= nums.length; i++) {
            long cur = i < nums.length ? nums[i] : (long) upper + 1;
            if (cur - prev >= 2) {
                res.add(Arrays.asList((int)(prev + 1), (int)(cur - 1)));
            }
            prev = cur;
        }
        return res;
    }
}

vector<vector<int>> findMissingRanges(vector<int>& nums, int lower, int upper) {
    vector<vector<int>> res;
    long long prev = (long long) lower - 1;
    for (int i = 0; i <= (int) nums.size(); i++) {
        long long cur = i < (int) nums.size() ? nums[i] : (long long) upper + 1;
        if (cur - prev >= 2) {
            res.push_back({(int)(prev + 1), (int)(cur - 1)});
        }
        prev = cur;
    }
    return res;
}

Explanation

The numbers in nums are like fence posts inside the range [lower, upper]. The missing numbers are exactly the gaps between consecutive posts. So we just walk through the sorted list and report each gap as a range.

The clever part is two sentinels that handle the edges cleanly. We start prev = lower - 1 (an imaginary post just below the range) and pretend there's a final post at upper + 1. This way the gaps before the first number and after the last number get caught by the same loop, with no special cases.

For each value cur, if cur - prev >= 2 there's a gap, so we emit [prev + 1, cur - 1]. A difference of exactly 1 means they're consecutive, so nothing is missing.

Example: nums=[0,1,3,50,75], range [0,99]. Between 1 and 3 the gap is [2,2]; between 3 and 50 it's [4,49].

Continuing past the last value 75 up to the sentinel 100 yields [76,99], giving the full answer in one pass.

Time: O(n) Space: O(1) extra (excluding output)