Missing Ranges

Problem

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are within the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the shortest sorted list of ranges that exactly covers all the missing numbers. That is, no element of nums is included in any of the ranges, and each missing number is covered by one of the ranges.

Constraints

• -109 <= lower <= upper <= 109
• 0 <= nums.length <= 100
• lower <= nums[i] <= upper
• All the values of nums are unique.

Solution

The problem Missing Ranges can be solved by simply checking for missing elements from the array. As all elements are guaranteed to be sorted, unique and to be within the inclusive range, all gaps between elements with a size of at least 2 are guaranteed to contain missing numbers.

Implementation

class Solution
{
  public:
    vector<vector<int>> findMissingRanges(vector<int> &nums, int lower, int upper)
    {
        if (nums.empty() || lower < nums.front())
            nums.insert(nums.begin(), lower - 1);
        if (nums.empty() || nums.back() < upper)
            nums.push_back(upper + 1);

        vector<vector<int>> ret;
        for (int i = 0; i < nums.size() - 1; i++)
            if (nums[i] < upper || lower < nums[i + 1])
                if (nums[i] + 1 <= nums[i + 1] - 1)
                {
                    vector<int> num = {nums[i] + 1, nums[i + 1] - 1};
                    ret.push_back(num);
                }

        return ret;
    }
};