Summary Ranges

Difficulty: Easy | Acceptance: 54.20% | Paid: No Topics: Array

You are given a sorted unique integer array nums.

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] should be output as:

“a->b” if a != b “a” if a == b

• Examples
• Constraints
• Approach 1: Linear Scan
• Approach 2: Two Pointers
• Approach 3: Brute Force

Examples

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
- -2^31 <= nums[i] <= 2^31 - 1
- All the values of nums are unique.
- nums is sorted in ascending order.

Approach 1: Linear Scan

Intuition We iterate through the array once. We keep track of the start of the current range. If the next number is not consecutive to the current one, the current range ends, and we add it to the result.

Steps

• Initialize an empty list res to store the result strings.
• Iterate through the nums array using index i.
• For each element, consider it as the start of a potential range.
• Extend the range as long as the next element is exactly 1 greater than the current element (nums[i+1] == nums[i] + 1).
• Once the consecutive sequence breaks, format the range from start to nums[i] and add it to res.
• Continue until the end of the array.

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        res = []
        i = 0
        n = len(nums)
        while i < n:
            start = nums[i]
            # Extend the range while numbers are consecutive
            while i + 1 < n and nums[i + 1] == nums[i] + 1:
                i += 1
            end = nums[i]
            if start == end:
                res.append(str(start))
            else:
                res.append(str(start) + "->" + str(end))
            i += 1
        return res

Complexity

• Time: O(n)
• Space: O(1) (excluding the space required for the output list)
• Notes: This is the most efficient approach, visiting each element at most twice (once by the outer loop and once by the inner loop).

Approach 2: Two Pointers

Intuition We use two pointers, start and end, to explicitly define the boundaries of the current range. We move the end pointer forward as long as the sequence remains consecutive.

Steps

• Initialize start pointer at 0.
• Use a while loop to iterate while start is less than the array length.
• Initialize end to be equal to start.
• Move end forward while nums[end + 1] equals nums[end] + 1.
• Format the string from nums[start] to nums[end] and add to result.
• Update start to end + 1 to begin checking the next range.

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        res = []
        n = len(nums)
        start = 0
        while start < n:
            end = start
            # Move end pointer to find the limit of the consecutive sequence
            while end + 1 < n and nums[end + 1] == nums[end] + 1:
                end += 1
            
            if start == end:
                res.append(str(nums[start]))
            else:
                res.append(str(nums[start]) + "->" + str(nums[end]))
            
            start = end + 1
        return res

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Logically similar to the Linear Scan approach, but uses explicit pointer variables for clarity.

Approach 3: Brute Force

Intuition For every number in the array, we check if it is already covered by a range we have previously added to our result list. If not, we scan forward to find the full range starting from that number.

Steps

• Initialize an empty result list.
• Iterate through each number num in nums.
• Check if num falls within any existing range in the result list.
• If it is covered, skip to the next number.
• If it is not covered, scan forward from num to find the end of the consecutive sequence.
• Add the new range to the result list.

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        res = []
        n = len(nums)
        for i in range(n):
            num = nums[i]
            # Check if current number is already covered by an existing range
            covered = False
            for r in res:
                parts = r.split("->")
                start = int(parts[0])
                end = int(parts[-1])
                if start <= num <= end:
                    covered = True
                    break
            
            if covered:
                continue
            
            # Find the end of the range starting at num
            end = num
            j = i + 1
            while j < n and nums[j] == end + 1:
                end = nums[j]
                j += 1
                
            if num == end:
                res.append(str(num))
            else:
                res.append(str(num) + "->" + str(end))
                
        return res

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: This approach is inefficient because for every element, we scan the result list (which can grow to size n) and potentially scan the array again. It is included here for completeness as a brute-force strategy.