Summary Ranges

Easy Arrays & Hashing Two Pointer Original on LeetCode

Reported atNetflixCisco

Summary Ranges is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (single pass with run start), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (inner loop per run) up.

Problem

You are given a sorted array nums of distinct integers. Split it into the fewest possible groups of consecutive integers (each group is a run like 4, 5, 6 with no gaps), and describe each group as a string:

  • "a->b" if the group runs from a to b with a != b,
  • "a" if the group is the single number a.

Return the list of these strings in increasing order.

Examples

Example 1

Input
nums = [-3, -2, -1, 4, 6, 7]
Output
["-3->-1", "4", "6->7"]
Why
-3, -2, -1 are consecutive; 4 stands alone; 6 and 7 form a pair.

Example 2

Input
nums = [10, 12, 13, 14, 20]
Output
["10", "12->14", "20"]
Why
Only 12, 13, 14 are consecutive, so 10 and 20 are single-number ranges.

Example 3

Input
nums = []
Output
[]
Why
No numbers, no ranges.

Constraints

  • 0 <= nums.length <= 20
  • -2^31 <= nums[i] <= 2^31 - 1
  • nums is sorted in strictly increasing order (all values are distinct).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (inner loop per run)O(n)O(1)
Optimal (single pass with run start)O(n)O(1)

1Brute force (inner loop per run)

TimeO(n)The inner index only moves forward, so each element is looked at a constant number of times.
SpaceO(1)Only indices besides the output list.

From each run start i, walk an inner index j forward while the next value is exactly one more than the current one. Emit the run nums[i]..nums[j], then jump i to j + 1.

  1. Set i = 0.
  2. While i < n: set j = i and advance j while j + 1 < n and nums[j + 1] == nums[j] + 1 (in 64-bit).
  3. Add "nums[i]" if i == j, else "nums[i]->nums[j]".
  4. Set i = j + 1.
class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        int i = 0, n = nums.length;
        while (i < n) {
            int j = i;
            while (j + 1 < n && (long) nums[j] + 1 == nums[j + 1]) j++;
            res.add(i == j ? String.valueOf(nums[i]) : nums[i] + "->" + nums[j]);
            i = j + 1;
        }
        return res;
    }
}

2Optimal (single pass with run start)

TimeO(n)One pass over the array.
SpaceO(1)Only the run start besides the output list.

Scan once, remembering the value where the current run started. At each index, check whether the run ends here: either it is the last element or the next value is not this value plus one. When it ends, emit it; the next element starts a new run.

  1. For each index i, if i == 0 or nums[i - 1] + 1 != nums[i] (in 64-bit), set start = nums[i].
  2. If i == n - 1 or nums[i] + 1 != nums[i + 1], close the run: add start alone or start->nums[i].
class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        int n = nums.length;
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || (long) nums[i - 1] + 1 != nums[i]) start = nums[i];
            boolean ends = i == n - 1 || (long) nums[i] + 1 != nums[i + 1];
            if (ends) res.add(start == nums[i] ? String.valueOf(start) : start + "->" + nums[i]);
        }
        return res;
    }
}

Edge cases to test

  • Empty array: return an empty list
  • One element: a single range without an arrow
  • The whole array is one run, like [5, 6, 7]
  • Values at the 32-bit limits: computing x + 1 can overflow, so compare with a wider type

Hints

Hint 1

A range ends exactly where the next number is not the previous number plus one.

Hint 2

Remember where the current run started; when the run breaks (or the array ends), write it out as either "a" or "a->b".

FAQ

What is the best time complexity for Summary Ranges?

Optimal (single pass with run start) runs in O(n) time and O(1) extra space. One pass over the array.

Which pattern does Summary Ranges use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Summary Ranges?

Yes. Brute force (inner loop per run) takes O(n) time and O(1) space. From each run start i, walk an inner index j forward while the next value is exactly one more than the current one.

Which edge cases should I test for Summary Ranges?

Empty array: return an empty list; One element: a single range without an arrow; The whole array is one run, like [5, 6, 7]; Values at the 32-bit limits: computing x + 1 can overflow, so compare with a wider type.