[Facebook Question] Missing Ranges

Problem: You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in 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 smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.

Each range [a,b] in the list should be output as:

"a->b" if a != b

"a" if a == b

Example:

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: ["2","4->49","51->74","76->99"]
Explanation: The ranges are:
[2,2] --> "2"
[4,49] --> "4->49"
[51,74] --> "51->74"
[76,99] --> "76->99"

Input: nums = [], lower = 1, upper = 2
Output: ["1->2]
Explanation: The only missing range is [1,2], which becomes "1->2".

Approach: We can simply scan the whole array and add the missing ranges in the result. Please note that:

• if nums[i] - nums[i - 1] > 1 then we know the missing range is [nums[i-1] + 1, nums[i] - 1]. 

We also need to take care of the conditions where lower < nums[0] and upper > nums[length - 1].

That's all!

Implementation in C#:

    public IList<string> FindMissingRanges(int[] nums, int lower, int upper) 

    {

        List<string> result = new List<string>();

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            result.Add(this.GenerateRange(lower, upper));

            return result;

        }

        if (lower < nums[0])

        {

            result.Add(this.GenerateRange(lower, nums[0] - 1));

        }

        for (int i = 1; i < length; ++i)

        {

            if (nums[i] - nums[i - 1] > 1)

            {

                result.Add(this.GenerateRange(nums[i - 1] + 1, nums[i] - 1));

            }

        } 

        if (upper > nums[length - 1])

        {

            result.Add(this.GenerateRange(nums[length - 1] + 1, upper));

        }

        return result;   

    }

    

    private string GenerateRange(int low, int high)

    {

        string range = low.ToString();

        if (high > low)

        {

            range += "->" + high;

        }

        return range;

    }

Complexity: O(n)