LeetCode 228: Summary Ranges

Problem Restatement

We are given a sorted array of unique integers called nums.

We need to return the smallest sorted list of ranges that covers every number in nums exactly once.

A range [a,b] means all integers from a to b, inclusive.

Each range should be written as:

For example, [0,1,2] becomes "0->2".

LeetCode states that nums is sorted, all values are unique, and nums.length can be 0. The values fit in signed 32-bit integer range.

Input and Output

Function shape:

class Solution:
    def summaryRanges(self, nums: list[int]) -> list[str]:
        ...

Examples

Example 1:

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

The consecutive groups are:

0, 1, 2   -> "0->2"
4, 5      -> "4->5"
7         -> "7"

Example 2:

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

The consecutive groups are:

0         -> "0"
2, 3, 4   -> "2->4"
6         -> "6"
8, 9      -> "8->9"

Example 3:

Input:  nums = []
Output: []

There are no numbers, so there are no ranges.

First Thought: Scan Consecutive Groups

Because the array is already sorted, consecutive ranges appear next to each other.

So we can scan from left to right.

When we start a range at index i, we keep moving forward while the next number is exactly one greater than the current number.

The current range ends when:

nums[j + 1] != nums[j] + 1

or when we reach the end of the array.

Key Insight

A range is determined by its first and last value.

For a consecutive group like:

2, 3, 4, 5

we only need:

start = 2
end = 5

Then the output is:

"2->5"

For a single value like:

7

the start and end are the same, so the output is:

"7"

This suggests a two-pointer scan:

Algorithm

Initialize an empty list ans.

Set i = 0.

While i is inside the array:

1. Set j = i.
2. Move j forward while the next number is consecutive.
3. Convert the range from nums[i] to nums[j] into a string.
4. Add the string to ans.
5. Set i = j + 1 to start the next range.

Range formatting rule:

if nums[i] == nums[j]:
    ans.append(str(nums[i]))
else:
    ans.append(f"{nums[i]}->{nums[j]}")

Correctness

We prove that the algorithm returns exactly the required summary ranges.

At the start of each loop, i points to the first number that has not yet been covered by a range.

The inner loop advances j as long as the next number is consecutive. Therefore, when the inner loop stops, the range from nums[i] to nums[j] is the longest possible consecutive range starting at nums[i].

The algorithm then outputs this range.

If i == j, the range contains one number, so the correct output is "a".

If i != j, the range contains more than one number, so the correct output is "a->b".

After adding the range, the algorithm sets:

i = j + 1

So every number in the finished range is skipped, and the next loop begins at the first uncovered number.

Because the array is sorted and unique, no later number can belong to a range that already ended. Therefore, each output range is maximal, ordered, and covers exactly the numbers in nums.

When the loop ends, all numbers have been covered exactly once.

Complexity

Here, n is the length of nums.

The output list itself may contain up to n strings.

Implementation

class Solution:
    def summaryRanges(self, nums: list[int]) -> list[str]:
        ans = []
        n = len(nums)
        i = 0

        while i < n:
            j = i

            while j + 1 < n and nums[j + 1] == nums[j] + 1:
                j += 1

            if i == j:
                ans.append(str(nums[i]))
            else:
                ans.append(f"{nums[i]}->{nums[j]}")

            i = j + 1

        return ans

Code Explanation

We start with:

ans = []
n = len(nums)
i = 0

ans stores the final range strings.

i marks the start of the current range.

For each range, we begin with:

j = i

Then we extend j while the next number continues the current range:

while j + 1 < n and nums[j + 1] == nums[j] + 1:
    j += 1

When this loop finishes, the current range is from nums[i] to nums[j].

If the range has only one number:

if i == j:
    ans.append(str(nums[i]))

Otherwise, format it with an arrow:

else:
    ans.append(f"{nums[i]}->{nums[j]}")

Then move to the next range:

i = j + 1

Finally:

return ans

Testing

def run_tests():
    s = Solution()

    assert s.summaryRanges([0, 1, 2, 4, 5, 7]) == ["0->2", "4->5", "7"]
    assert s.summaryRanges([0, 2, 3, 4, 6, 8, 9]) == ["0", "2->4", "6", "8->9"]
    assert s.summaryRanges([]) == []
    assert s.summaryRanges([5]) == ["5"]
    assert s.summaryRanges([-3, -2, -1, 1, 2]) == ["-3->-1", "1->2"]
    assert s.summaryRanges([-2147483648, -2147483647, 2147483647]) == [
        "-2147483648->-2147483647",
        "2147483647",
    ]

    print("all tests passed")

run_tests()