We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Missing Ranges

Number: 163

Difficulty: Easy

Paid? Yes

Companies: Meta, Google, TikTok

Problem Description

Given an inclusive range [lower, upper] and a sorted, unique integer array nums (with all its elements within the range), find the shortest sorted list of ranges that exactly covers all the numbers missing from nums. Each missing number must be included in one of the ranges and none of the numbers in nums should be part of any range.

Key Insights

  • Use a pointer (or iterate index) to traverse the nums array while keeping track of the previous number considered.
  • Check for missing numbers before the first element, between consecutive elements, and after the last element.
  • When a gap is found, convert it to a range string that is either a single number (if the gap is exactly one number) or an interval.
  • Handle edge cases when the nums array is empty.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the nums array, since we iterate through the array once. Space Complexity: O(1) additional space (ignoring the output list), as we only use a few extra variables.

Solution

The solution leverages a single pass through the input array and calculates the missing ranges by comparing the expected number with the current number in nums. First, initialize a variable "prev" to one less than the lower bound so that missing numbers from the very start of the range can be handled uniformly. For each number in the array, if there is a gap between prev and the current number (i.e., current number is at least 2 more than prev), then add the missing range (prev+1 to current number-1) to the output list. Update "prev" to the current number and finally handle any gap between the last number and the upper bound. The primary data structures used are the list for the output; the approach is iterative.

Code Solutions

# Python solution for Missing Ranges problem

def findMissingRanges(nums, lower, upper):
    missing_ranges = []  # List to store the missing range intervals
    prev = lower - 1  # Initialize previous value to one less than lower

    # Append a sentinel at the end for easier gap handling
    nums.append(upper + 1)

    # Loop through each number, including the sentinel
    for num in nums:
        # If there is a gap between previous and current number
        if num - prev >= 2:
            # If gap is of single number, add that number as a range
            if num - prev == 2:
                missing_ranges.append([prev + 1, prev + 1])
            else:
                missing_ranges.append([prev + 1, num - 1])
        prev = num  # Update previous to current
    return missing_ranges

# Example usage:
print(findMissingRanges([0,1,3,50,75], 0, 99))
← Back to All Questions