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:

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.
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.
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:

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.
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.
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.
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.
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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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.

Handling Empty Array: First, we check if nums is empty, which it is not. So, we continue with further steps.
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.
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).
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.
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

1from typing import List
2
3class Solution:
4    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]:
5        # Initialize the size of the nums array
6        num_elements = len(nums)
7      
8        # If nums is empty, return the entire range from lower to upper
9        if num_elements == 0:
10            return [[lower, upper]]
11      
12        # List to store the missing ranges
13        missing_ranges = []
14      
15        # Check if there is a missing range before the start of the array
16        if nums[0] > lower:
17            missing_ranges.append([lower, nums[0] - 1])
18      
19        # Use zip to create pairs of sequential elements (a, b) and loop through
20        for a, b in zip(nums, nums[1:]):
21            # If there is a gap greater than one between the two numbers, a missing range is found
22            if b - a > 1:
23                missing_ranges.append([a + 1, b - 1])
24      
25        # Check if there is a missing range after the end of the array
26        if nums[-1] < upper:
27            missing_ranges.append([nums[-1] + 1, upper])
28      
29        # Return the list of missing ranges
30        return missing_ranges
31

1import java.util.List;
2import java.util.ArrayList;
3
4class Solution {
5  
6    /**
7     * Finds the missing ranges between the given array elements and the specified lower and upper bounds.
8     *
9     * @param nums  The array of integers where missing ranges are to be found.
10     * @param lower The lower bound of the range to find missing elements for.
11     * @param upper The upper bound of the range to find missing elements for.
12     * @return A list of lists containing the start and end of each missing range.
13     */
14    public List<List<Integer>> findMissingRanges(int[] nums, int lower, int upper) {
15        // Initialize the length of the nums array.
16        int n = nums.length;
17
18        // Handle the edge case where the input array is empty.
19        if (n == 0) {
20            // The entire range from lower to upper is missing.
21            return List.of(List.of(lower, upper));
22        }
23
24        // This list will store the missing ranges.
25        List<List<Integer>> missingRanges = new ArrayList<>();
26
27        // Check if there is a missing range before the first element.
28        if (nums[0] > lower) {
29            // Add the range from lower to the element before the first number in the array.
30            missingRanges.add(List.of(lower, nums[0] - 1));
31        }
32
33        // Loop over the array to find missing ranges between the numbers.
34        for (int i = 1; i < n; ++i) {
35            // Check if the current element and the previous element are not consecutive.
36            if (nums[i] - nums[i - 1] > 1) {
37                // Add the range from the element after the previous number to the element before the current number.
38                missingRanges.add(List.of(nums[i - 1] + 1, nums[i] - 1));
39            }
40        }
41
42        // Check if there is a missing range after the last element.
43        if (nums[n - 1] < upper) {
44            // Add the range from the element after the last number in the array to the upper bound.
45            missingRanges.add(List.of(nums[n - 1] + 1, upper));
46        }
47
48        // Return the list of missing ranges.
49        return missingRanges;
50    }
51}
52

1#include <vector>
2
3class Solution {
4public:
5    // Function to find missing ranges between lower and upper bounds
6    std::vector<std::vector<int>> findMissingRanges(std::vector<int>& nums, int lower, int upper) {
7        // Get the size of the input vector
8        int size = nums.size();
9      
10        // If the input vector is empty, return a vector with the complete range
11        if (size == 0) {
12            return {{lower, upper}};
13        }
14      
15        // Initialize the answer vector
16        std::vector<std::vector<int>> missingRanges;
17
18        // Handle the case where the first element is greater than the lower bound
19        if (nums[0] > lower) {
20            missingRanges.push_back({lower, nums[0] - 1});
21        }
22
23        // Iterate over the input vector to find the missing ranges
24        for (int i = 1; i < size; ++i) {
25            // Check if there is a missing range between consecutive numbers
26            if (nums[i] - nums[i - 1] > 1) {
27                // Add the missing range to the answer vector
28                missingRanges.push_back({nums[i - 1] + 1, nums[i] - 1});
29            }
30        }
31      
32        // Handle the case where the last element is less than the upper bound
33        if (nums[size - 1] < upper) {
34            missingRanges.push_back({nums[size - 1] + 1, upper});
35        }
36      
37        // Return the final vector of missing ranges
38        return missingRanges;
39    }
40};
41

1// Function to find missing ranges in a sorted array of numbers.
2// It returns a list of missing ranges between the lower and upper bounds, inclusive.
3function findMissingRanges(nums: number[], lower: number, upper: number): number[][] {
4    const length = nums.length; // Get the length of the input array
5    const missingRanges: number[][] = []; // Initialize an array to hold missing ranges
6
7    // Handle the case where the input array is empty.
8    // If so, the entire range between lower and upper is missing.
9    if (length === 0) {
10        return [[lower, upper]];
11    }
12
13    // Check if there is a missing range before the first element.
14    if (nums[0] > lower) {
15        missingRanges.push([lower, nums[0] - 1]);
16    }
17
18    // Iterate through the array to find missing ranges between consecutive elements.
19    for (let i = 1; i < length; ++i) {
20        // If there is a gap greater than 1 between two consecutive numbers,
21        // then there is a missing range between them.
22        if (nums[i] - nums[i - 1] > 1) {
23            missingRanges.push([nums[i - 1] + 1, nums[i] - 1]);
24        }
25    }
26
27    // Check if there is a missing range after the last element.
28    if (nums[length - 1] < upper) {
29        missingRanges.push([nums[length - 1] + 1, upper]);
30    }
31
32    // Return the list of missing ranges.
33    return missingRanges;
34}
35

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don't know