You are given a sorted unique integer array nums where elements are in the inclusive range [lower, upper].
Return the smallest sorted list of ranges that cover all the missing numbers in the range [lower, upper].
A range [a,b] is represented by:
"a->b" if a != b"a" if a == bExample 1:
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"
Example 2:
Input: nums = [-1], lower = -1, upper = -1 Output: [] Explanation: There are no missing ranges since there are no missing numbers.
Constraints:
0 <= nums.length <= 100-109 <= lower <= upper <= 109nums are unique.nums is sorted in ascending order.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach to finding missing ranges involves checking every possible number within the defined range to see if it's present in the given numbers. If a number is not found, we consider it as part of a missing range. We continue this exhaustive check to identify all missing ranges.
Here's how the algorithm would work step-by-step:
def find_missing_ranges_brute_force(numbers, lower_bound, upper_bound):
missing_ranges = []
start_range = lower_bound
# Iterate through each number within the specified range
for current_number in range(lower_bound, upper_bound + 1):
is_number_present = False
for number in numbers:
if current_number == number:
is_number_present = True
break
# Check if the current number is missing
if not is_number_present:
continue
# A present number signifies the end of a potential range
if start_range < current_number:
if start_range == current_number - 1:
missing_ranges.append(str(start_range))
else:
missing_ranges.append(str(start_range) + "->" + str(current_number - 1))
start_range = current_number + 1
# Handle the case where the missing range extends to the upper bound
if start_range <= upper_bound:
if start_range == upper_bound:
missing_ranges.append(str(start_range))
else:
missing_ranges.append(str(start_range) + "->" + str(upper_bound))
return missing_rangesThe problem asks us to find gaps between numbers in a given sequence and represent those gaps as ranges. The clever idea is to walk through the numbers and compare each number to what we expect next. If they don't match, we've found a range to add to our results.
Here's how the algorithm would work step-by-step:
def find_missing_ranges(numbers, lower_bound, upper_bound):
result = []
next_expected_number = lower_bound
for i in range(len(numbers)):
number = numbers[i]
# Gap found before the current number.
if number > next_expected_number:
result.append(format_range(next_expected_number, number - 1))
# Advance the next expected number.
if number >= next_expected_number:
next_expected_number = number + 1
# Gap found after the last number.
if next_expected_number <= upper_bound:
result.append(format_range(next_expected_number, upper_bound))
return result
def format_range(lower_range, upper_range):
if lower_range == upper_range:
return str(lower_range)
else:
return str(lower_range) + "->" + str(upper_range)| Case | How to Handle |
|---|---|
| Null or empty input array | Return an empty list immediately as there are no numbers to form ranges. |
| nums is null but lower and upper bounds are specified | Return the entire range if lower and upper are different, otherwise return empty list. |
| Single element in the array | Compare the single element with lower and upper to determine if there's a missing range before, after, or both. |
| Array with min and max integer values for boundary conditions | Handle integer overflow when adding or subtracting one from min/max values to form range boundaries. |
| All numbers in array are the same | Compare the identical number to lower and upper to check missing ranges before or after the number. |
| Lower bound is greater than upper bound | Return an empty list as this represents an invalid range. |
| All numbers in the array fall within the specified range | Adjust the start/end boundaries when forming missing ranges according to if the first/last number are on boundaries or not. |
| No missing ranges exist within the given bounds and array. | Return an empty list as all values in the range are accounted for within the provided array. |