Missing Ranges

Easy

Google

2 views

Topics:

Arrays

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

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: ["2->2","4->49","51->74","76->99"]
Explanation: The ranges are:
[2,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 the array contains -1 and it equals lower and upper.

Could you provide an algorithm to find the missing ranges with optimal time and space complexity? What are the edge cases to consider, and how would you handle potential integer overflow issues if lower and upper are very large? Can you provide code?

Missing Ranges

Easy

Google

2 views

Topics:

Arrays

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

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: ["2->2","4->49","51->74","76->99"]
Explanation: The ranges are:
[2,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 the array contains -1 and it equals lower and upper.

Could you provide an algorithm to find the missing ranges with optimal time and space complexity? What are the edge cases to consider, and how would you handle potential integer overflow issues if lower and upper are very large? Can you provide code?

Solution

Clarifying Questions

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:

What are the inclusive lower and upper bounds of the overall range (lower and upper)?
Can the input array `nums` contain numbers outside the defined range [lower, upper]?
Can the input array `nums` be empty or null?
If there are no missing ranges, what should I return (e.g., an empty list)?
Are the numbers in the input array `nums` guaranteed to be sorted in ascending order?

Brute Force Solution

Approach

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:

Begin by examining each whole number, one by one, starting from the lower limit of the specified range.
For each number, check if it exists within the provided list of numbers.
If the number is not present in the list, mark it as a potential starting point for a missing range.
Continue checking subsequent numbers until you encounter a number that *is* present in the list, or until you reach the upper limit of the range.
If a sequence of missing numbers is identified, record the start and end of that missing range.
Repeat this process for all the numbers between the lower and upper limits to find all missing ranges.

Code Implementation

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_ranges

Big(O) Analysis

Time Complexity

O(n*(upper-lower)) – The described brute force approach iterates through all numbers within the range [lower, upper], which has a size of (upper - lower + 1). For each number in this range, we check its presence in the input array nums, which contains n elements. This check involves iterating through the nums array. Therefore, the outer loop runs approximately (upper - lower + 1) times, and the inner loop (searching in nums) runs n times in the worst case. The total number of operations approximates n * (upper - lower + 1), which simplifies to O(n * (upper - lower)).

Space Complexity

O(1) – The brute force approach, as described, iterates through the range and checks each number against the input list. It only requires a few variables to store the lower limit, the upper limit, the current number being checked, and potentially the start and end of a missing range. The number of variables used does not depend on the size of the input list (N). Therefore, the auxiliary space used is constant, resulting in a space complexity of O(1).

Optimal Solution

Approach

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

Imagine the numbers are laid out in a line, and we are walking along that line.
Start by expecting the first number in the overall range, which is given to us as a starting point.
Look at the first actual number in our given sequence of numbers.
If the number we're expecting is smaller than the number we actually see, we know there's a gap. Record that gap as a range.
If the number we're expecting is the same as the number we see, that's fine, no gap. We just update what number we're expecting next.
Now, look at the next number in our sequence.
Again, compare the number we're expecting with the number we see. If they differ, record a gap, or update the expected number.
Keep doing this until you reach the end of the numbers.
After you've looked at all the numbers, see if the last number you saw is less than the upper limit of the overall range given to us. If it is, there's a final gap at the end, so record that too.
The collection of recorded gaps is our result.

Code Implementation

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)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums once. The loop's body performs constant-time operations: comparing expected values and formatting range strings. The number of iterations is directly proportional to the size of the input array, denoted as n. Therefore, the time complexity is O(n).

Space Complexity

O(R) – The primary space consumption comes from storing the ranges of missing numbers in a result list. In the worst-case scenario, where nearly every number is missing, the number of ranges could be proportional to the difference between the upper and lower bounds of the overall range, which we can represent as R (upper bound - lower bound + 1). Therefore, the auxiliary space used by the result list is O(R), where R is the range of possible values.

Edge Cases

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.