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.

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 a run of neighbours in the array, and it ends exactly where two neighbours differ by more than 1. No range can cross such a gap, so cutting at every gap gives the fewest ranges.

Check both neighbours of every value

Intuition

A range opens at a value that is first, or whose left neighbour is not one less. It closes at a value that is last, or whose right neighbour is not one more. In [0, 1, 2, 5, 6, 9], ranges open at 0, 5 and 9 and close at 2, 6 and 9.

Remember the value where the current range opened. When it closes at nums[i], write "start->nums[i]", or only "start" when it opened and closed on the same value, as 9 does.

Each value looks at its two neighbours once: O(n) time, and one remembered start for O(1) extra space.

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

Find the two ends of each range. Pointer i stands on its first value. Pointer j starts at i and moves right while the next value is exactly one more, so it stops on the last value. Then i jumps to j+1.

For [-3, -1, 0, 1, 4, 7, 8]: at -3 the next value -1 is not -2, so "-3" stands alone. From -1, j moves over 0 and 1 and stops before 4: "-1->1". Then come "4" and "7->8".

Both pointers only move forward, so the inner loop runs n times in total: O(n) time and O(1) extra space.

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

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 questions3

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.

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 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.

def summaryRanges(nums):
    # Write code here

Test #1

Test #2

Argument

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

Expected Output

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