# 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:

| Case | Output Format |
|---|---|
| `a == b` | `"a"` |
| `a != b` | `"a->b"` |

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

| Item | Meaning |
|---|---|
| Input | A sorted unique integer array `nums` |
| Output | A list of strings |
| Range format | `"a->b"` for multiple numbers, `"a"` for one number |
| Empty input | Return an empty list |

Function shape:

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

## Examples

Example 1:

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

The consecutive groups are:

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

Example 2:

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

The consecutive groups are:

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

Example 3:

```text
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:

```python
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:

```text
2, 3, 4, 5
```

we only need:

```text
start = 2
end = 5
```

Then the output is:

```text
"2->5"
```

For a single value like:

```text
7
```

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

```text
"7"
```

This suggests a two-pointer scan:

| Pointer | Meaning |
|---|---|
| `i` | Start index of the current range |
| `j` | End index of the current range |

## 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:

```python
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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each element is visited once |
| Space | `O(1)` | Extra space is constant, ignoring the output list |

Here, `n` is the length of `nums`.

The output list itself may contain up to `n` strings.

## Implementation

```python
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:

```python
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:

```python
j = i
```

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

```python
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:

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

Otherwise, format it with an arrow:

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

Then move to the next range:

```python
i = j + 1
```

Finally:

```python
return ans
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `[0,1,2,4,5,7]` | Standard mixed ranges |
| `[0,2,3,4,6,8,9]` | Starts with single value |
| `[]` | Empty input |
| `[5]` | Single element |
| Negative values | Consecutive logic works below zero |
| 32-bit boundary values | Checks large integer formatting |