LeetCode Solutions Blog

Summary Ranges

Number: 228

Difficulty: Easy

Paid? No

Problem Description

Given a sorted unique integer array nums, return the smallest sorted list of ranges that exactly covers all the numbers in the array. A range [a,b] is represented as "a->b" if a != b, and "a" if a == b.

Key Insights

Since the array is sorted and unique, we can simply iterate through it.
Track the start of a new range, and expand the range as long as the next number is consecutive.
When a break in consecutiveness is noticed, format the current range accordingly and start a new range.
Finalize the last range after exiting the loop.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the nums array. Space Complexity: O(1) additional space (excluding the space for the output list).

Solution

We iterate through the array while maintaining a start pointer for the current range. For each element, check if the next element is exactly one greater. If not, the current range ends here. Format the range as "start->end" if there is more than one element in the range, otherwise just as "start". This algorithm leverages the sorted property of the array to accomplish the task in one pass using constant extra space.

Code Solutions

# Function to summarize ranges in a sorted unique integer array.
def summary_ranges(nums):
    ranges = []  # List to store the resulting range strings
    n = len(nums)
    i = 0  # Pointer to iterate through nums
    
    # Iterate over the numbers in the array
    while i < n:
        start = nums[i]  # Start of a new range
        # Traverse the consecutive sequence
        while i + 1 < n and nums[i + 1] == nums[i] + 1:
            i += 1
        end = nums[i]  # End of the current range
        # If start and end are the same, it's a single element range
        if start == end:
            ranges.append(str(start))
        else:
            ranges.append(f"{start}->{end}")
        i += 1  # Move to the next number after the current range
    return ranges

# Example test cases
print(summary_ranges([0,1,2,4,5,7]))  # Output: ["0->2", "4->5", "7"]
print(summary_ranges([0,2,3,4,6,8,9]))  # Output: ["0", "2->4", "6", "8->9"]