Summary Ranges
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 fromatobwitha != b,"a"if the group is the single numbera.
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 - 1numsis 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(n)The inner index only moves forward, so each element is looked at a constant number of times.O(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.
- Set i = 0.
- While i < n: set j = i and advance j while j + 1 < n and nums[j + 1] == nums[j] + 1 (in 64-bit).
- Add
"nums[i]"if i == j, else"nums[i]->nums[j]". - 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;
}
}class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
res = []
i, n = 0, len(nums)
while i < n:
j = i
while j + 1 < n and nums[j] + 1 == nums[j + 1]:
j += 1
res.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
i = j + 1
return resclass Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> res;
int i = 0, n = nums.size();
while (i < n) {
int j = i;
while (j + 1 < n && (long long)nums[j] + 1 == nums[j + 1]) j++;
res.push_back(i == j ? to_string(nums[i]) : to_string(nums[i]) + "->" + to_string(nums[j]));
i = j + 1;
}
return res;
}
};function summaryRanges(nums) {
const res = [];
let i = 0;
const n = nums.length;
while (i < n) {
let j = i;
while (j + 1 < n && nums[j] + 1 === nums[j + 1]) j++;
res.push(i === j ? String(nums[i]) : `${nums[i]}->${nums[j]}`);
i = j + 1;
}
return res;
}2Optimal (single pass with run start)
O(n)One pass over the array.O(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.
- For each index i, if i == 0 or nums[i - 1] + 1 != nums[i] (in 64-bit), set start = nums[i].
- If i == n - 1 or nums[i] + 1 != nums[i + 1], close the run: add
startalone orstart->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;
}
}class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
res = []
n = len(nums)
start = 0
for i in range(n):
if i == 0 or nums[i - 1] + 1 != nums[i]:
start = nums[i]
if i == n - 1 or nums[i] + 1 != nums[i + 1]:
res.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
return resclass Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> res;
int n = nums.size();
int start = 0;
for (int i = 0; i < n; i++) {
if (i == 0 || (long long)nums[i - 1] + 1 != nums[i]) start = nums[i];
bool ends = i == n - 1 || (long long)nums[i] + 1 != nums[i + 1];
if (ends) res.push_back(start == nums[i] ? to_string(start) : to_string(start) + "->" + to_string(nums[i]));
}
return res;
}
};function summaryRanges(nums) {
const res = [];
const n = nums.length;
let start = 0;
for (let i = 0; i < n; i++) {
if (i === 0 || nums[i - 1] + 1 !== nums[i]) start = nums[i];
const ends = i === n - 1 || nums[i] + 1 !== nums[i + 1];
if (ends) res.push(start === nums[i] ? String(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 + 1can 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.