Summary Ranges

Difficulty: Easy
Topics: Array
Link: https://leetcode.com/problems/summary-ranges/

Problem Description

You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

"a->b" if a != b
"a" if a == b

Example 1:


Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

Example 2:


Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

Constraints:

0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
All the values of nums are unique.
nums is sorted in ascending order.

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement
Given a sorted array nums of unique integers, partition the array into minimal consecutive segments where each segment represents either:

A single element x (when isolated)
A continuous interval [a,b] (when consecutive elements exist)
Formally:
Let R be the output list of ranges. Then:

∪_{r∈R} r = {nums[0], nums[1], ..., nums[n-1]} (coverage)
∀r_i,r_j∈R, r_i ∩ r_j = ∅ (disjointness)
Each r is either {a} or {a,a+1,...,b} (range structure)
Output format: "a" if |r|=1, else "a->b"

Beginner-Friendly Explanation
Imagine you have a sorted list of numbers with no duplicates. Your task is to group them into “ranges” where consecutive numbers belong together. For example:

Numbers 0,1,2 become “0->2”
A single number 7 becomes “7”
Gaps between numbers create new ranges
The output should be the shortest possible list of these ranges that includes all numbers exactly once.

Mathematical Formulation
Let nums be a sorted sequence a₀ < a₁ < ... < aₙ₋₁. Define a range partition P = {I₁, I₂, ..., Iₖ} where:

I_j = [aₚ, a_q] with a_{i+1} = a_i + 1 for all p ≤ i < q
⋃_{j=1}^k I_j = {a₀, a₁, ..., aₙ₋₁}
I_j ∩ I_m = ∅ for j ≠ m
Minimize k subject to these constraints.

Constraint Analysis

0 <= nums.length <= 20:
- Allows O(n²) solutions comfortably
- Edge case: empty array → return []
-2³¹ <= nums[i] <= 2³¹-1:
- Requires 64-bit integer handling
- No overflow concerns in Python but relevant for typed languages
Unique values: Eliminates duplicate-handling complexity
Sorted ascending: Enables single-pass solutions; unsorted variant would be harder

2. Intuition Scaffolding

Real-World Metaphor
Think of organizing books on a shelf where some volumes are missing. If you have volumes 1,2,3,5,6,8, you’d label them as “1-3”, “5-6”, “8” rather than listing each individually.

Gaming Analogy
In a game’s level selection screen, completed levels might show as “1-5”, “7”, “9-12” instead of showing every number when levels are consecutive.

Math Analogy
Finding connected components in a graph where edges exist between consecutive integers present in the array.

Common Pitfalls

Off-by-one errors when checking consecutive numbers
Forgetting empty input case
Handling single-element ranges incorrectly
Modifying array during iteration
Overcomplicating with unnecessary data structures

3. Approach Encyclopedia

Brute Force

def summaryRanges(nums):
    if not nums:
        return []
    
    result = []
    i = 0
    while i < len(nums):
        start = nums[i]
        # Expand range as far as possible
        while i + 1 < len(nums) and nums[i+1] == nums[i] + 1:
            i += 1
        end = nums[i]
        
        if start == end:
            result.append(str(start))
        else:
            result.append(f"{start}->{end}")
        
        i += 1
    
    return result

Complexity Proof

Time: O(n) - each element visited once
Space: O(1) auxiliary (O(n) output storage)
Mathematical: Let n = len(nums). The inner while loop increments i, ensuring at most n total iterations.

Visualization

nums: [0,1,2,4,5,7]
       ↑ start=0
       → → → (expand while consecutive)
           ↑ end=2 → "0->2"
             ↑ start=4  
             → → (expand)
                 ↑ end=5 → "4->5"
                   ↑ start=7 → "7"

4. Code Deep Dive

def summaryRanges(nums):
    if not nums:  # Handle empty array edge case
        return []
    
    result = []
    i = 0
    n = len(nums)
    
    while i < n:
        start = nums[i]  # Beginning of current range
        
        # Expand range while numbers are consecutive
        while i + 1 < n and nums[i+1] == nums[i] + 1:
            i += 1
        
        end = nums[i]  # End of current range
        
        # Format based on range length
        if start == end:
            result.append(str(start))
        else:
            result.append(f"{start}->{end}")
        
        i += 1  # Move to next potential range
    
    return result

Edge Case Handling

Empty array: Early return [] (line 2-3)
Single element: start == end condition (line 15)
Maximum range: Handled by while loop (line 8-9)
Negative numbers: No special handling needed due to consecutive check

5. Complexity War Room

Hardware-Aware Analysis
With n ≤ 20, the entire algorithm fits in L1 cache (~64KB). Memory usage is negligible.

Approach Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n)	O(1)	10/10	✅ Perfect
Two Pointer	O(n)	O(1)	9/10	✅ Good
Recursive	O(n)	O(n)	6/10	❌ Overkill

6. Pro Mode Extras

Variants

Unsorted Input: Sort first O(n log n)
Duplicate Values: Need to skip duplicates
Multiple Range Queries: Preprocess with union-find
Streaming Input: Maintain ranges in sorted data structure

Interview Cheat Sheet

First Mention: “This can be solved in O(n) time with O(1) space using a single pass”
Key Insight: “Consecutive numbers form ranges; gaps break them”
Testing: Always test empty, single element, all consecutive, no consecutive cases

#228 - Summary Ranges