Problem Description

You are given a sorted array of unique integers nums. Your task is to find the smallest list of ranges that covers all numbers in the array exactly.

A range [a,b] represents all integers from a to b inclusive. For example, the range [1,3] includes the numbers 1, 2, and 3.

The goal is to group consecutive numbers in the array into ranges. Each number in nums must belong to exactly one range, and the ranges should cover only the numbers that exist in nums (no extra numbers).

The output format for each range depends on whether it contains a single number or multiple numbers:

• If a range contains only one number (like [5,5]), output it as "5"
• If a range contains multiple numbers (like [1,3]), output it as "1->3"

For example:

• If nums = [0,1,2,4,5,7], the consecutive groups are [0,1,2], [4,5], and [7]
• The output would be ["0->2", "4->5", "7"]

The ranges must be returned in sorted order (which naturally happens when processing the sorted input array from left to right).

Intuition

Since the array is already sorted, consecutive numbers that form a range will appear next to each other. This makes the problem straightforward - we just need to identify where consecutive sequences start and end.

Think of walking through the sorted array and grouping numbers that are exactly 1 apart. When we encounter a number that isn't exactly 1 more than the previous number, we know we've found a break point between ranges.

For example, in [0,1,2,4,5,7]:

• Starting at 0: we see 1 (which is 0+1), then 2 (which is 1+1) - these are consecutive
• At 4: this is not 2+1, so we've found a break. The range [0,2] ends here
• Starting at 4: we see 5 (which is 4+1) - these are consecutive
• At 7: this is not 5+1, so we've found another break. The range [4,5] ends here
• 7 stands alone as a single-element range

The key insight is using two pointers: one (i) marks the start of a potential range, and another (j) extends as far as possible while numbers remain consecutive. When we can't extend j anymore (because nums[j+1] ≠ nums[j]+1), we've found a complete range from i to j.

After recording this range, we move i to where j left off plus one position, and repeat the process. This ensures we examine each element exactly once while building our ranges efficiently.

Solution Approach

The solution uses a two-pointer technique to efficiently identify consecutive ranges in the sorted array.

Algorithm Steps:

1. Initialize pointers and result list: Start with pointer i at index 0 and create an empty list ans to store the range strings.

2. Main loop: While i is within the array bounds:

   • Set j = i to mark the potential end of the current range
   • Extend the range: Keep moving j to the right while:
     • j + 1 < n (not at the end of array)
     • nums[j + 1] == nums[j] + 1 (next number is consecutive)
   • Format the range: Once we can't extend further, we have found a complete range from index i to j:
     • If i == j: single element range, add str(nums[i]) to result
     • If i != j: multi-element range, add f'{nums[i]}->{nums[j]}' to result
   • Move to next range: Set i = j + 1 to start searching for the next range

3. Return the result: The ans list contains all ranges in order.

Helper Function: The code uses a helper function f(i, j) to format the range string:

def f(i: int, j: int) -> str:
    return str(nums[i]) if i == j else f'{nums[i]}->{nums[j]}'

Example Walkthrough with nums = [0,1,2,4,5,7]:

• Round 1: i=0, extend j from 0→1→2 (stops at 2 because 4 ≠ 3), add "0->2"
• Round 2: i=3, extend j from 3→4 (stops at 4 because 7 ≠ 6), add "4->5"
• Round 3: i=5, j stays at 5 (can't extend), add "7"
• Result: ["0->2", "4->5", "7"]

Time Complexity: O(n) where n is the length of the array. Each element is visited exactly once.

Space Complexity: O(1) excluding the output array, as we only use a constant amount of extra space for pointers.

Example Walkthrough

Let's walk through the solution with nums = [0,2,3,4,6,8,9]:

Initial State:

• Array: [0,2,3,4,6,8,9]
• i = 0, ans = []

Round 1: Start at index i = 0 (value = 0)

• Set j = 0
• Check if we can extend: nums[1] = 2, which is not 0 + 1
• Can't extend, so range is just [0]
• Since i == j, format as "0"
• Add "0" to result
• Move i = j + 1 = 1

Round 2: Start at index i = 1 (value = 2)

• Set j = 1
• Check if we can extend: nums[2] = 3, which equals 2 + 1 ✓
• Extend j = 2
• Check if we can extend: nums[3] = 4, which equals 3 + 1 ✓
• Extend j = 3
• Check if we can extend: nums[4] = 6, which is not 4 + 1
• Can't extend further, so range is [2,3,4]
• Since i ≠ j (1 ≠ 3), format as "2->4"
• Add "2->4" to result
• Move i = j + 1 = 4

Round 3: Start at index i = 4 (value = 6)

• Set j = 4
• Check if we can extend: nums[5] = 8, which is not 6 + 1
• Can't extend, so range is just [6]
• Since i == j, format as "6"
• Add "6" to result
• Move i = j + 1 = 5

Round 4: Start at index i = 5 (value = 8)

• Set j = 5
• Check if we can extend: nums[6] = 9, which equals 8 + 1 ✓
• Extend j = 6
• Check if we can extend: j + 1 = 7 is out of bounds
• Can't extend further, so range is [8,9]
• Since i ≠ j (5 ≠ 6), format as "8->9"
• Add "8->9" to result
• Move i = j + 1 = 7

Termination: i = 7 is out of bounds, exit loop

Final Result: ["0", "2->4", "6", "8->9"]

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

• The outer while loop iterates through each element in the array exactly once. The variable i starts at 0 and jumps to j + 1 after each iteration, where j marks the end of a consecutive range.
• The inner while loop also visits each element at most once throughout the entire execution. Although it appears nested, each element is checked only once for consecutiveness with its next element.
• The helper function f(i, j) runs in O(1) time as it performs a simple string concatenation or returns a single string value.
• Therefore, the total time complexity is O(n).

Space Complexity: O(1) auxiliary space (excluding the output).

• The algorithm uses a constant amount of extra space with variables i, j, and n.
• The helper function f doesn't use any additional space beyond the string it creates for the output.
• The space used by the output list ans is O(k) where k is the number of ranges, but this is not counted as auxiliary space since it's required for the output.
• In the worst case where no consecutive numbers exist, k = n, making the output space O(n).
• Therefore, the auxiliary space complexity is O(1).

Common Pitfalls

1. Forgetting to Handle Empty Array

One of the most common oversights is not checking if the input array is empty before processing.

Problem Code:

def summaryRanges(self, nums: List[int]) -> List[str]:
    current_idx = 0
    array_length = len(nums)
    result = []
  
    while current_idx < array_length:  # This works but could be more explicit
        # ... rest of code

Why it's a pitfall: While the above code technically handles empty arrays correctly (the while loop won't execute), it's not immediately obvious and could lead to confusion during code reviews or debugging.

Better Solution:

def summaryRanges(self, nums: List[int]) -> List[str]:
    # Explicitly handle empty array
    if not nums:
        return []
  
    current_idx = 0
    array_length = len(nums)
    result = []
    # ... rest of code

2. Off-by-One Error in Range Extension

A critical mistake is incorrectly checking the consecutive condition, especially with the array bounds.

Problem Code:

# WRONG: Checking nums[range_end_idx] instead of nums[range_end_idx + 1]
while range_end_idx < array_length and nums[range_end_idx] == nums[range_end_idx - 1] + 1:
    range_end_idx += 1

Why it's a pitfall: This compares the current element with the previous one incorrectly and can cause index out of bounds errors or incorrect range detection.

Correct Solution:

# Check if the NEXT element is consecutive to current
while range_end_idx + 1 < array_length and nums[range_end_idx + 1] == nums[range_end_idx] + 1:
    range_end_idx += 1

3. Integer Overflow with Large Numbers

When dealing with very large integers near the maximum integer value, adding 1 could theoretically cause overflow in some languages.

Problem Code:

# In languages with fixed integer sizes, this could overflow
if nums[j + 1] == nums[j] + 1:

Why it's a pitfall: In Python, this isn't actually an issue due to arbitrary precision integers, but in languages like Java or C++, adding 1 to Integer.MAX_VALUE causes overflow.

Defensive Solution:

# More defensive approach using subtraction instead of addition
while range_end_idx + 1 < array_length and nums[range_end_idx + 1] - nums[range_end_idx] == 1:
    range_end_idx += 1

4. Incorrect String Formatting

Using the wrong string formatting can lead to incorrect output format.

Problem Code:

# WRONG: Using comma or space instead of arrow
return f'{nums[start_idx]},{nums[end_idx]}'  # Wrong: "0,2"
return f'{nums[start_idx]} {nums[end_idx]}'   # Wrong: "0 2"
return f'{nums[start_idx]}-{nums[end_idx]}'   # Wrong: "0-2" (single dash)

Correct Solution:

# Must use arrow notation with two characters "->"
return f'{nums[start_idx]}->{nums[end_idx]}'  # Correct: "0->2"

5. Not Preserving Original Array Order

Some might be tempted to use a different approach that doesn't maintain the sorted order.

Problem Code:

# WRONG: Processing ranges in reverse or random order
result = []
# ... some logic that adds ranges out of order
return sorted(result)  # Trying to fix order afterwards

Why it's a pitfall: The problem requires ranges to be in sorted order. Processing the sorted input array from left to right naturally maintains this order without additional sorting.

Correct Approach: Always process the array from left to right (index 0 to n-1) to maintain the natural sorted order of ranges.