163. Missing Ranges
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 27.4%
Problem Breakdown
The problem requires identifying missing ranges in a given inclusive range [lower, upper] that are not present in a sorted unique integer array nums. The output should be the smallest sorted list of ranges covering all missing numbers. Each range should be formatted as "a->b" if a != b, or simply "a" if a == b.
Inputs:
- A sorted unique integer array
nums. - An inclusive lower bound
lower. - An inclusive upper bound
upper.
Outputs:
- A list of strings representing the missing ranges.
Implicit Constraints and Edge Cases:
- The array
numscan be empty. - The range
[lower, upper]can include negative numbers. - The range can span a large number of integers, up to (10^9).
- The array
numsis sorted and contains unique elements.
Intuition
A brute-force approach would involve iterating through every integer in the range [lower, upper] and checking if it exists in nums. This approach is inefficient due to its linear time complexity relative to the size of the range. Instead, we can leverage the fact that nums is sorted to identify gaps between consecutive elements efficiently.
The key insight is to iterate through nums and check for gaps between each pair of consecutive numbers (including the gap before the first element and after the last element). If a gap exists, we format it as a range and add it to the result list.
Approach
- Initialize an empty list
resultto store the missing ranges. - Iterate through
numswith two pointers:previnitialized tolower - 1andcurrinitialized to each element innums. - For each pair
(prev, curr), check if there is a gap:- If
prev + 1 < curr, add the range"prev+1->curr-1"toresult. - If
prev + 1 == curr, add the single number"prev+1"toresult.
- If
- After the loop, handle the gap after the last element in
nums:- If
prev + 1 < upper, add the range"prev+1->upper"toresult. - If
prev + 1 == upper, add the single number"prev+1"toresult.
- If
- Return the
resultlist.
Complexity Analysis
- Time Complexity: (O(n)), where (n) is the length of
nums. We iterate throughnumsonce. - Space Complexity: (O(1)) for the additional variables used, excluding the space required for the output list.
Solution
def findMissingRanges(nums, lower, upper):
result = []
prev = lower - 1
for curr in nums:
if prev + 1 < curr:
result.append(f"{prev+1}->{curr-1}")
elif prev + 1 == curr:
result.append(str(prev+1))
prev = curr
if prev + 1 < upper:
result.append(f"{prev+1}->{upper}")
elif prev + 1 == upper:
result.append(str(prev+1))
return result
Edge Cases Handled
- Empty
nums: The loop does not execute, and the final check handles the entire range[lower, upper]. - Single element in
nums: The loop processes one element, and the final check handles any remaining range. - No missing ranges: If all numbers from
lowertoupperare present innums, the result remains empty. - Negative numbers: The algorithm correctly handles negative numbers by using arithmetic operations.
- Large range: The algorithm efficiently processes large ranges due to its linear time complexity.