Summary Ranges

Q: What is the time complexity of Summary Ranges?

O(n) . Each value is visited once, and each range is written once. Apart from the output list, the extra space is O(1) : the start of the current range and an index or two.

EasyIntervals Arrays and strings

+10

You get a sorted array nums of distinct integers. Split it into the fewest ranges of consecutive integers, so that every value belongs to exactly one range. Write a range a..b as the text "a->b", or as "a" when it holds one value. Return the ranges in increasing order.

Function

summaryRanges(nums: integer-array) → string-array

numsinteger-array: the sorted array of distinct integers
Returnsstring-array: the ranges as text, from the smallest values to the largest

Constraints

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums is sorted in increasing order and has no duplicates.

Examples

Input: nums = [0, 1, 2, 5, 6, 9]
Output: ["0->2", "5->6", "9"]
Explanation: 0, 1, 2 follow each other, so they form "0->2". The jump from 2 to 5 starts a new range, "5->6", and 9 stands alone as "9".

Input: nums = [-3, -1, 0, 1, 4, 7, 8]
Output: ["-3", "-1->1", "4", "7->8"]
Explanation: -3 has no neighbour (-2 is missing), -1, 0, 1 form a run, 4 stands alone, and 7, 8 close the list. Negative values work the same way: -1 is followed by -1 + 1 = 0.

+16 hidden tests on Submit

Follow-up

Suppose nums could hold duplicates, like [1, 2, 2, 3]. What would you change so that it still prints "1->3"?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Because the values are sorted and distinct, a range of consecutive integers is always a run of neighbours in the array, and a range ends exactly where two neighbours differ by more than 1. Cutting the array at every such gap gives the fewest ranges, since no range can cross a gap. What is left is careful bookkeeping: the start of each run, the last element, and the text format.

Check both neighbours of every value

Intuition

Look at one value at a time and ask two questions. Does a range open here? Yes, when this is the first value or the value before it is not one less. Does a range close here? Yes, when this is the last value or the value after it is not one more.

In [0, 1, 2, 5, 6, 9], a range opens at 0, 5 and 9, and closes at 2, 6 and 9. Remember the value where the current range opened. When a range closes at nums[i], write "start->nums[i]", or only "start" when the range opened and closed on the same value, as 9 does.

Every value is visited once and looks at two neighbours, so the time is O(n). Apart from the output, you keep one remembered start, so the extra space is O(1).

Algorithm

Set start = nums[0].
For each index i: if i > 0 and nums[i] != nums[i-1] + 1, set start = nums[i].
If i is the last index or nums[i+1] != nums[i] + 1, the range closes here.
Append "start" when start == nums[i], otherwise "start->nums[i]".
Return the list after the last index.

def summaryRanges(nums):
    n = len(nums)
    ranges = []
    start = nums[0]
    for i in range(n):
        # A range opens where the value before is not one less.
        if i > 0 and nums[i] != nums[i - 1] + 1:
            start = nums[i]
        # A range closes where the value after is not one more.
        if i == n - 1 or nums[i + 1] != nums[i] + 1:
            ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
    return ranges

Two pointers over each run

Intuition

Treat each range as a block of the array and find its two ends. Pointer i stands on the first value of a range. Pointer j starts at i and moves right while the next value is exactly one more, so it stops on the last value of the range.

For [-3, -1, 0, 1, 4, 7, 8]: i at -3 cannot extend, because -1 is not -2, so the range is "-3". Then i jumps to -1, and j moves over 0 and 1 and stops before 4: "-1->1". Then "4" and "7->8". After each range, i moves to j+1, the first value of the next one.

The ranges are as few as possible: two values separated by a gap can never share a range, and the method only splits at gaps. Both pointers only move forward, so the inner loop runs n times in total across all ranges, which keeps the time at O(n) and the extra space at O(1).

Algorithm

Set i = 0.
Set j = i, and move j right while j+1 < n and nums[j+1] == nums[j] + 1.
Append "nums[i]" when i == j, otherwise "nums[i]->nums[j]".
Set i = j + 1 and repeat until i passes the end.
Return the list.

def summaryRanges(nums):
    ranges = []
    n = len(nums)
    i = 0
    while i < n:
        # i is the first value of a run; push j to its last value.
        j = i
        while j + 1 < n and nums[j + 1] == nums[j] + 1:
            j += 1
        ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
        # The next run starts right after this one.
        i = j + 1
    return ranges

Pitfalls and edge cases

The logic fits in a few lines; the mistakes are at the edges.

Forgetting the last range. A loop that writes a range only when it meets a gap never writes the final one, so [0, 1, 2, 5, 6, 9] loses its "9". Close a range at the last index too.
Writing "a->a" for a single value. A range of one value is written as "a".
Printing large values in scientific notation. R turns a double like 1000000000 into 1e+09; convert the values to integers before you paste them.

Frequently asked questions4

What is the time complexity of Summary Ranges?

O(n). Each value is visited once, and each range is written once. Apart from the output list, the extra space is O(1): the start of the current range and an index or two.

Why does cutting at every gap give the fewest ranges?

A range holds consecutive integers, so it cannot contain two values with a missing number between them. Every gap in the sorted array must therefore separate two ranges, and with g gaps you need at least g+1 ranges. Cutting only at the gaps gives exactly g+1.

How do you handle a range with only one number?

Check whether the range starts and ends on the same value. If it does, write that value alone, like "9". If not, write the start, the arrow and the end, like "5->6". With two pointers, the test is i == j.

Does Summary Ranges need the input to be sorted?

Yes. The method only compares neighbours, so it relies on consecutive integers sitting next to each other. For unsorted input, sort it first, which makes the whole task O(n log n), or put the values in a hash set and grow each range from its smallest value, as in the longest consecutive sequence problem.

Python

def summaryRanges(nums):
    # Write code here

Test cases

Case 1

Case 2

Input

nums = [0, 1, 2, 5, 6, 9]

Expected

["0->2", "5->6", "9"]