LeetCode 228: Summary Ranges - All Solutions Explained

Problem Statement

Given a sorted unique integer array nums, return the smallest sorted list of ranges that cover all the numbers in the array exactly. Each range [a,b] should be listed as: - "a->b" if a != b - "a" if a == b

Copy codeInput: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]

Input: nums = []
Output: []

Explanation

This approach uses two pointers to track the start and end of each range: 1. Initialize start pointer at first element 2. Iterate through array with end pointer 3. When non-consecutive numbers found, add current range to result 4. Update start pointer to new element 5. Handle single-element ranges separately

Step-by-Step Example

For [0,1,2,4,5,7]: 1. start=0, i=1: 1 is consecutive (0→1) 2. i=2: 2 is consecutive (0→2) 3. i=3: 4 breaks sequence → add "0->2" 4. start=4, i=4: 5 is consecutive (4→5) 5. i=5: 7 breaks sequence → add "4->5" 6. start=7 → add "7"

Python Implementation

Copy codedef summaryRanges(nums: list[int]) -> list[str]:
    if not nums:
        return []

    res = []
    start = nums[0]

    for i in range(1, len(nums)):
        if nums[i] != nums[i-1] + 1:
            if start == nums[i-1]:
                res.append(str(start))
            else:
                res.append(f"{start}->{nums[i-1]}")
            start = nums[i]

    # Handle last range
    if start == nums[-1]:
        res.append(str(start))
    else:
        res.append(f"{start}->{nums[-1]}")

    return res

Complexity Analysis

• Time Complexity: O(n) - single pass through array
• Space Complexity: O(1) - constant extra space (excluding output)
• Why Optimal: Efficient and easy to understand

Solution 2: Groupby Approach (Pythonic Alternative)

Explanation

This solution uses Python's itertools.groupby to identify consecutive sequences: 1. Group numbers where each differs from its index by same amount 2. Extract ranges from these groups 3. Format ranges appropriately

Python Implementation

Copy codefrom itertools import groupby

def summaryRanges(nums: list[int]) -> list[str]:
    res = []
    for _, g in groupby(enumerate(nums), lambda x: x[1] - x[0]):
        group = list(g)
        if len(group) > 1:
            res.append(f"{group[0][1]}->{group[-1][1]}")
        else:
            res.append(str(group[0][1]))
    return res

Complexity Analysis

• Time Complexity: O(n) - single pass with groupby
• Space Complexity: O(n) - temporary group storage
• Pros: Very concise Python code
• Cons: Less intuitive, depends on language features

Edge Cases to Consider

1. Empty array: Return empty list
2. Single element: Return single-element list
3. All consecutive: Single range "a->b"
4. No consecutive: All single-element ranges
5. Negative numbers: Handle negative ranges correctly

Performance Comparison

Final Recommendations

• Two Pointers solution is preferred for interviews - demonstrates algorithm skills
• Groupby solution is excellent for Python production code
• Both solutions show different approaches to sequence detection
• The problem tests array traversal and edge case handling