228. Summary Ranges
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 42.7%
Problem Breakdown
The problem requires us to take a sorted array of unique integers and return a list of ranges that cover all numbers in the array exactly. Each range should be represented as a string in the format "a->b" if a is not equal to b, or simply "a" if they are equal. The input array can be empty, contain only one element, or have multiple elements with gaps between them.
Inputs:
- A sorted list of unique integers
nums.
Outputs:
- A list of strings representing the ranges.
Implicit Constraints/Edge Cases:
- If the input list is empty, return an empty list.
- If the input list contains only one element, return a single-element list with that number as a string.
- Handle negative numbers and large integers within the given constraints.
Intuition
A brute-force approach would involve iterating through the array and checking each pair of consecutive elements to see if they form a range. This would be inefficient because it doesn’t take advantage of the sorted nature of the array. Instead, we can use a single pass through the array to identify contiguous ranges by checking if the difference between consecutive elements is 1.
The key insight is that we can maintain two pointers: one for the start of a potential range and another for the end. As we iterate through the array, we update these pointers to track when a range starts and ends. This approach ensures that we only traverse the list once, making it efficient in terms of both time and space.
Approach
- Initialize an empty list
resultto store the ranges. - Use two pointers:
startto mark the beginning of a range andendto track the current position in the array. - Iterate through the array:
- If the current element is consecutive to the previous one (
nums[end] == nums[end-1] + 1), increment theendpointer. - Otherwise, add the current range
[start, end-1]to the result list and updatestartto the current position.
- If the current element is consecutive to the previous one (
- After the loop, add the last range to the result list.
- Convert each range to the appropriate string format and return the result.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input array. We make a single pass through the array.
- Space Complexity: O(1) for the additional variables used, excluding the space required for the output list.
Solution
def summaryRanges(nums):
if not nums:
return []
result = []
start = end = 0
while end < len(nums):
# Check if the current element is consecutive to the previous one
if end > 0 and nums[end] != nums[end - 1] + 1:
# Add the range [start, end-1] to the result
if start == end - 1:
result.append(f"{nums[start]}")
else:
result.append(f"{nums[start]}->{nums[end-1]}")
# Update start to the current position
start = end
end += 1
# Add the last range to the result
if start == end - 1:
result.append(f"{nums[start]}")
else:
result.append(f"{nums[start]}->{nums[end-1]}")
return result
Edge Cases Handled
- Empty Input: Returns an empty list.
- Single Element: Returns a single-element list with the number as a string.
- Consecutive Elements: Correctly identifies and formats ranges of consecutive numbers.
- Non-Consecutive Elements: Handles gaps between numbers by starting new ranges.
- Negative Numbers and Large Integers: The solution works within the given constraints.