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 thenums
? 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
andupper
.
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 fromlower
toupper
is missing. We return this as a single range. -
Check Lower Bound: If
nums
is not empty, check if there's a gap betweenlower
and the first element ofnums
. If a gap exists, this forms our first missing range. -
Iterate Through
nums
: Use Python'spairwise
generator to loop through pairs of consecutive elements innums
. Thepairwise
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)
, ifb - a > 1
, we have found a gap which means there are missing numbers betweena
andb
. Each of these gaps forms a range that goes froma + 1
tob - 1
; these are appended to our answer list. -
Check Upper Bound: Finally, check if there's a gap between the last element of
nums
andupper
. If there is, the gap from the last number plus one toupper
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 EvaluatorExample 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 sincelower = 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 usepairwise
onnums
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.
- For the pair
-
Check Upper Bound: Lastly, we check after the last element in
nums
, which is 9. Theupper
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.
In a binary min heap, the minimum element can be found in:
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!