163. Missing Ranges

Problem Description

In this problem, you have two integers lower and upper representing the inclusive range of numbers. Also, you have an array nums which is sorted and contains unique integers that are within the given range. Some numbers within the range [lower, upper] might not be present in the nums array, and these numbers are considered "missing." The goal is to find the smallest sorted list of ranges, where each range covers the missing numbers without overlapping with any of the numbers in nums. The resulting ranges should together cover exactly all the missing numbers without any gaps or duplicates.

For example, if the lower is 0, upper is 99, and nums is [7, 28, 63], then the missing numbers are from 0 to 6, 8 to 27, and 29 to 62, and 64 to 99. You need to return these missing ranges in a sorted manner which could look like [[0, 6], [8, 27], [29, 62], [64, 99]].

Intuition

The solution involves a direct simulation of the problem by iterating through the elements in the array nums and identifying the gaps between the consecutive numbers as well as the gaps between the lower, upper limits, and the first and last number in nums.

Firstly, if the nums array is empty, the missing range is simply from lower to upper. However, if the array is not empty, we check for the following:

1. Is there a gap between lower and the first element of the nums? If so, this forms a range that needs to be added to the answer.
2. We then iterate over the given array, checking the difference between each pair of consecutive numbers. If the difference is more than 1, we've found a gap (missing numbers) and thus a range. These gaps are then made into ranges and added to the answer.
3. Lastly, we check for a potential gap between the last element of the nums and upper.

By handling both ends and the gaps in between, we're able to construct a list of ranges that covers all the missing numbers within the [lower, upper] range without including any number from nums.

Solution Approach

The implementation of the solution involves iterating over the elements in nums alongside handling the edge cases around lower and upper bounds. Here's the detailed walkthrough:

1. Handling Empty Array: If nums is empty, there are no numbers to compare against, hence the entire range from lower to upper is missing. We return this as a single range.

2. Check Lower Bound: If nums is not empty, check if there's a gap between lower and the first element of nums. If a gap exists, this forms our first missing range.

3. Iterate Through nums: Use Python's pairwise generator to loop through pairs of consecutive elements in nums. The pairwise utility yields tuples containing pairs of consecutive elements, which allows us to compare each pair without manual index management.

4. Find Gaps Between Numbers: For each consecutive pair (a, b), if b - a > 1, we have found a gap which means there are missing numbers between a and b. Each of these gaps forms a range that goes from a + 1 to b - 1; these are appended to our answer list.

5. Check Upper Bound: Finally, check if there's a gap between the last element of nums and upper. If there is, the gap from the last number plus one to upper is our final missing range.

The algorithm utilizes simple iteration and comparison with a focus on edge cases before and after the main loop. It takes advantage of Python's pairwise which is part of the itertools module (in Python versions 3.10 and later). The pairwise function makes these comparisons easier and the code more readable. However, if you are working with a Python version older than 3.10, you can manually compare elements using a loop with index i and i+1.

By applying these steps, we can ensure that all missing ranges are found and returned in the format of a list of lists, where each nested list contains two elements indicating the start and end of the missing range.

Example Walkthrough

Let's apply the solution approach to a simple example where lower = 1, upper = 10, and nums = [2, 3, 7, 9]. We expect to find the missing ranges that are not covered by numbers in nums.

1. Handling Empty Array: First, we check if nums is empty, which it is not. So, we continue with further steps.

2. Check Lower Bound: We look for gaps starting from the lower bound. The first element of nums is 2, and since lower = 1, we have a missing range [1, 1] which is essentially just the number 1.

3. Iterate Through nums: Now we iterate through the array and compare consecutive elements. We'll use pairwise on nums which would give us the pairs (2, 3), (3, 7), and (7, 9).

4. Find Gaps Between Numbers:

   • For the pair (2, 3), there is no gap since 3 - 2 is 1, indicating they are consecutive.
   • For (3, 7), we have a gap because 7 - 3 is greater than 1. The missing range is [4, 6].
   • For (7, 9), there is no gap since 9 - 7 is 2, indicating only one number (8) between them, and it's not considered a range.

5. Check Upper Bound: Lastly, we check after the last element in nums, which is 9. The upper bound is 10, so we have a missing number [10, 10], indicating just the number 10.

After applying the solution approach, we can conclude the missing ranges are [[1, 1], [4, 6], [10, 10]]. Each range encompasses the missing numbers without overlapping with any of the numbers in nums, satisfying the problem requirement.

Solution Implementation

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the array nums. This is because the script iterates over the array once with a single loop through pairwise(nums) and two additional checks at the beginning and end.

The space complexity, disregarding the output list, is O(1). This constant space complexity is due to only using a fixed amount of extra space (variables such as n and ans, which are negligible as their sizes do not scale with the input).

Learn more about how to find time and space complexity quickly using problem constraints.