#228 Summary Ranges
the problem
In plain words
nums is sorted in increasing order and has no duplicates. Describe it with the fewest ranges, in order: a run of consecutive numbers a, a+1, …, b becomes "a->b", and a number on its own becomes "a".
in nums = [0,1,2,4,5,7]
out ["0->2","4->5","7"]
0,1,2 is one run; 4,5 is another; 7 stands alone.
in nums = [0,2,3,4,6,8,9]
out ["0","2->4","6","8->9"]
- 0 ≤ nums.length ≤ 20
- −2³¹ ≤ nums[i] ≤ 2³¹ − 1
- Sorted in increasing order, all values unique
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternInterval merging (sort by start)
The input is already sorted, so each run of consecutive numbers is one stretch of the array. Grow a run while the next number is exactly one more; when it isn't, close the range.
solutions
From brute force to optimal
A number starts a run if x − 1 is missing. From there, keep searching the array for x + 1, x + 2, ….
- For each x: if x − 1 is in the array, skip it.
- Otherwise extend end while end + 1 is in the array (linear search).
- Emit "x" or "x->end".
Each value triggers linear searches over the array, and every value of a run is searched once.
Besides the output list.
class Solution { public List<String> summaryRanges(int[] nums) { List<String> out = new ArrayList<>(); for (int x : nums) { if (contains(nums, (long) x - 1)) continue; // not the start of a run long end = x; while (contains(nums, end + 1)) end++; // walk the run by searching for each next value out.add(end == x ? String.valueOf(x) : x + "->" + end); } return out; } /** Linear search. long, because x + 1 at Integer.MAX_VALUE would wrap to MIN_VALUE in int. */ private boolean contains(int[] nums, long v) { for (int y : nums) if (y == v) return true; return false; }}Walk the array. Remember where a run starts, and move forward while the next number is exactly one more.
- start = nums[i].
- While nums[i] + 1 == nums[i + 1]: i++.
- Emit start or start->nums[i]; continue from i + 1.
Every index is visited once.
Besides the output list (at most n strings).
class Solution { public List<String> summaryRanges(int[] nums) { List<String> out = new ArrayList<>(); int i = 0; while (i < nums.length) { int start = nums[i]; // nums[i] < nums[i + 1] <= MAX_VALUE, so nums[i] + 1 cannot overflow here while (i + 1 < nums.length && nums[i] + 1 == nums[i + 1]) i++; // stretch the run out.add(start == nums[i] ? String.valueOf(start) : start + "->" + nums[i]); i++; // next run starts after it } return out; }}in the room
How to say it in the interview
talk track
- Point out that the array is sorted, so consecutive values are neighbours in the array.
- Stretch with an inner while loop, emit the range, continue after it.
- Mention overflow:
nums[i] + 1is safe here because a bigger number follows it.
traps
- Adding 1 to Integer.MAX_VALUE elsewhere: it wraps to MIN_VALUE. Here
nums[i] + 1is only evaluated when a bigger number follows, so it's safe. - Forgetting to emit the last run when you emit only "on change".
what they ask next
Follow-ups
Numbers arrive one at a time (a stream)?
Keep the ranges in a TreeMap<start, end> and merge with the floor/ceiling neighbours in O(log n) per number (LC 352).
Unsorted input?
Sort first (O(n log n)), or put everything in a HashSet and grow runs from numbers whose x − 1 is missing, as in Longest Consecutive Sequence.
before you submit
Edge cases to test
- Empty array → empty list.
- [MIN_VALUE, MAX_VALUE] → two separate ranges. MAX_VALUE + 1 would wrap around to MIN_VALUE.
- Negative runs print like "-3->-1".
practise next
Similar problems
- #128Longest Consecutive SequenceMediumin Hashing
- #56Merge IntervalsMediumin Intervals