LeetCode Problem 228

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 228, Summary Ranges

Problem Understanding

The problem gives us a sorted array of unique integers and asks us to summarize consecutive values into compact range strings.

A range represents a continuous sequence of integers. For example, the numbers [4,5,6] can be represented as "4->6" because every integer between 4 and 6 exists in the array. A single isolated value such as 7 should simply be represented as "7".

The important detail is that the output must cover every number exactly once, without including numbers that are not present in the array. Since the input is already sorted and contains no duplicates, consecutive ranges can be identified by checking whether the next number is exactly one greater than the current number.

For example:

• [0,1,2] becomes "0->2"
• [7] becomes "7"
• [4,5] becomes "4->5"

The input array can be empty, which means the answer should also be an empty list.

The constraints are very small, with at most 20 numbers, but the goal is still to design a clean and efficient solution. The sorted and unique guarantees are extremely important because they simplify the problem significantly:

• Since the array is sorted, consecutive numbers always appear next to each other.
• Since the values are unique, we never need to worry about duplicates interfering with range detection.

Several edge cases are important:

• An empty array should return [].
• A single element array should return a list containing only that number as a string.
• Arrays where every number is consecutive should produce exactly one range.
• Arrays where no numbers are consecutive should produce only single-number ranges.
• Negative values must work correctly as well.

Approaches

Brute Force Approach

A brute force approach would attempt to build ranges by repeatedly checking every possible continuation for each starting point. For every number, we could scan forward until the sequence breaks, then restart from the next unused number.

This works because the input is sorted, so consecutive numbers appear together. However, the implementation can become inefficient if we repeatedly rescan portions of the array or perform redundant comparisons.

For example, if we start at index i, we may scan all the way to the end to find the range boundary. Then later iterations may revisit many of the same elements again.

Although the constraints are tiny in this problem, this style of repeated scanning can lead to quadratic behavior in larger inputs.

Optimal Approach

The key observation is that each number only needs to be processed once.

Because the array is sorted and unique, a range ends exactly when the next number is not equal to the current number plus one.

This means we can scan the array from left to right using a single pass:

• Record the start of the current range.
• Continue moving forward while numbers remain consecutive.
• Once the sequence breaks, finalize the current range string.
• Start a new range from the next number.

This approach is efficient because every element is visited only once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) excluding output	Repeatedly rescans portions of the array
Optimal	O(n)	O(1) excluding output	Single pass through the array

Algorithm Walkthrough

1. Create an empty result list that will store the final range strings.
2. Handle the array from left to right using an index pointer. Each iteration begins by marking the current number as the start of a new range.
3. Store the current value as range_start. This value will remain fixed while we attempt to extend the range.
4. Move the index forward while the next number is consecutive. Two numbers are consecutive if:

nums[i + 1] == nums[i] + 1

As long as this condition holds, the current range continues. 5. When the consecutive sequence ends, the current number becomes the end of the range. 6. If the start and end are the same value, append a single number string such as "7". 7. Otherwise, append a range string such as "4->6". 8. Continue scanning from the next unprocessed number until the entire array has been handled.

Why it works

The algorithm maintains the invariant that every processed element belongs to exactly one completed range.

Because the array is sorted and unique, every consecutive sequence appears as one contiguous block. The inner loop expands the range until the sequence breaks, guaranteeing that the produced range is maximal. Since the algorithm advances past all processed elements before starting the next range, no number is skipped or duplicated.

Python Solution

from typing import List

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        result: List[str] = []
        n = len(nums)
        index = 0

        while index < n:
            range_start = nums[index]

            while (
                index + 1 < n
                and nums[index + 1] == nums[index] + 1
            ):
                index += 1

            range_end = nums[index]

            if range_start == range_end:
                result.append(str(range_start))
            else:
                result.append(f"{range_start}->{range_end}")

            index += 1

        return result

The implementation begins by initializing an empty result list and an index pointer.

The outer while loop processes one range at a time. At the beginning of each iteration, the current value becomes the start of the range.

The inner loop extends the range as long as consecutive numbers continue appearing. Since the array is sorted, consecutive values must appear immediately next to each other.

After the loop finishes, the current index points to the final value in the range. The code then decides whether the range contains a single value or multiple values.

If both ends are equal, the output format is just the number itself. Otherwise, the range is formatted using "start->end".

Finally, the index moves forward to begin processing the next range.

Go Solution

package main

import "strconv"

func summaryRanges(nums []int) []string {
	result := []string{}
	n := len(nums)
	index := 0

	for index < n {
		rangeStart := nums[index]

		for index+1 < n && nums[index+1] == nums[index]+1 {
			index++
		}

		rangeEnd := nums[index]

		if rangeStart == rangeEnd {
			result = append(result, strconv.Itoa(rangeStart))
		} else {
			rangeString := strconv.Itoa(rangeStart) + "->" + strconv.Itoa(rangeEnd)
			result = append(result, rangeString)
		}

		index++
	}

	return result
}

The Go implementation follows exactly the same logic as the Python solution.

One notable difference is string conversion. Go requires strconv.Itoa() to convert integers into strings.

The result is stored in a slice of strings. An empty input naturally returns an empty slice because the loop never executes.

The integer comparison is safe because the constraints fit within Go's standard integer range on LeetCode systems.

Worked Examples

Example 1

Input:

nums = [0,1,2,4,5,7]

Initial state:

Variable	Value
result	[]
index	0

First Range

Step	index	Current Value	Action
Start range	0	0	range_start = 0
Check next	1	1	consecutive
Check next	2	2	consecutive
Stop	2	2	next value is 4

Range becomes:

0->2

Result:

["0->2"]

Second Range

Step	index	Current Value	Action
Start range	3	4	range_start = 4
Check next	4	5	consecutive
Stop	4	5	next value is 7

Range becomes:

4->5

Result:

["0->2", "4->5"]

Third Range

Step	index	Current Value	Action
Start range	5	7	single value
Stop	5	7	end of array

Range becomes:

7

Final result:

["0->2", "4->5", "7"]

Example 2

Input:

nums = [0,2,3,4,6,8,9]

First Range

Step	index	Current Value	Action
Start range	0	0	single value
Stop	0	0	next value is 2

Result:

["0"]

Second Range

Step	index	Current Value	Action
Start range	1	2	range_start = 2
Check next	2	3	consecutive
Check next	3	4	consecutive
Stop	3	4	next value is 6

Result:

["0", "2->4"]

Third Range

Step	index	Current Value	Action
Start range	4	6	single value
Stop	4	6	next value is 8

Result:

["0", "2->4", "6"]

Fourth Range

Step	index	Current Value	Action
Start range	5	8	range_start = 8
Check next	6	9	consecutive
Stop	6	9	end of array

Final result:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every element is processed exactly once
Space	O(1) excluding output	Only a few variables are used

The algorithm performs a single linear scan through the array. Although there is a nested loop, the index only moves forward, never backward. This means each element participates in at most one iteration of the inner loop.

The extra memory usage is constant because the algorithm only stores a few tracking variables. The output list itself is not counted in auxiliary space complexity.

Test Cases

from typing import List

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        result: List[str] = []
        n = len(nums)
        index = 0

        while index < n:
            range_start = nums[index]

            while (
                index + 1 < n
                and nums[index + 1] == nums[index] + 1
            ):
                index += 1

            range_end = nums[index]

            if range_start == range_end:
                result.append(str(range_start))
            else:
                result.append(f"{range_start}->{range_end}")

            index += 1

        return result

solution = Solution()

assert solution.summaryRanges([0,1,2,4,5,7]) == ["0->2","4->5","7"]  # basic mixed ranges
assert solution.summaryRanges([0,2,3,4,6,8,9]) == ["0","2->4","6","8->9"]  # alternating singles and ranges
assert solution.summaryRanges([]) == []  # empty input
assert solution.summaryRanges([5]) == ["5"]  # single element
assert solution.summaryRanges([1,2,3,4]) == ["1->4"]  # one large range
assert solution.summaryRanges([1,3,5,7]) == ["1","3","5","7"]  # no consecutive numbers
assert solution.summaryRanges([-3,-2,-1,1,2,4]) == ["-3->-1","1->2","4"]  # negative values
assert solution.summaryRanges([0,1,3,4,5,7,8,10]) == ["0->1","3->5","7->8","10"]  # multiple separate ranges
assert solution.summaryRanges([-2147483648,-2147483647,2147483647]) == ["-2147483648->-2147483647","2147483647"]  # integer boundary values

Test	Why
[0,1,2,4,5,7]	Validates normal mixed behavior
[0,2,3,4,6,8,9]	Tests alternating singletons and ranges
[]	Ensures empty input works
[5]	Tests single element handling
[1,2,3,4]	Ensures one full range is formed
[1,3,5,7]	Ensures isolated values remain separate
[-3,-2,-1,1,2,4]	Verifies negative number handling
[0,1,3,4,5,7,8,10]	Tests multiple disjoint ranges
Extreme integer values	Confirms boundary correctness

Edge Cases

Empty Array

An empty input is one of the easiest places for implementations to fail if they assume at least one element exists.

For example, accessing nums[0] without checking the array length would cause an index error. This implementation avoids that problem because the outer loop only executes when index < n. If n is zero, the loop body never runs, and the function correctly returns an empty list.

Single Element Array

When the array contains only one value, the algorithm must return a single-number string instead of a range format.

For example:

[7] -> ["7"]

A common bug is always formatting output as "start->end", which would incorrectly produce "7->7". The implementation explicitly checks whether the range start and range end are equal before deciding how to format the result.

No Consecutive Numbers

Arrays like [1,3,5,7] contain no consecutive pairs at all.

In this case, every number should become its own separate range. The inner loop immediately stops for each element because the next number is never equal to the current number plus one.

The implementation naturally handles this because every iteration creates a one-element range.

Entire Array Is One Range

Arrays like [1,2,3,4,5] test whether the algorithm can correctly extend a range all the way to the end of the array.

A common mistake is failing to finalize the last range after the loop finishes. This implementation avoids that issue because the range is added immediately after the inner loop ends, even if the sequence continued until the final element.