MiddleCodeOccasionalNot answered yet
Collapse a list of integers into a range string
Given a list of distinct non-negative integers, return a string that collapses runs of consecutive integers into ranges. [1,4,3,2,5,6,8,9,11] (after sorting) → "1-6,8-9,11". A single integer is printed alone, not as "k-k".
Requirements:
- Sort first (input is unsorted, no duplicates). Handle empty input and the final range.
std::string summaryRanges(std::vector<int> nums) {
// your code here
}Write the implementation.
Sort the array. Walk it tracking the start of the current consecutive run; when the next value is not prev + 1, flush the run as start or start-end and begin a new one. Flush the last run after the loop. O(n log n) for the sort, O(n) to build.
- ✗Forgetting to sort, so non-adjacent consecutive values are missed
- ✗Printing a singleton as
k-kinstead of justk - ✗Dropping the final range because it is flushed only inside the loop
- →How would duplicates change the logic if they were allowed?
- →Why is flushing after the loop necessary?
Contents
Task
Collapse a list of integers into a range string like "1-6,8-9,11".
Solution
std::string summaryRanges(std::vector<int> nums) {
if (nums.empty()) return "";
std::sort(nums.begin(), nums.end());
std::string out;
int start = nums[0];
for (size_t i = 1; i <= nums.size(); ++i) {
if (i == nums.size() || nums[i] != nums[i-1] + 1) {
if (!out.empty()) out += ",";
int end = nums[i-1];
out += std::to_string(start);
if (end != start) out += "-" + std::to_string(end);
if (i < nums.size()) start = nums[i];
}
}
return out;
}Key points
- Sort, then group consecutive values via
prev + 1. - Print a singleton as
k, notk-k. - Flush the final range when reaching the end of the array.
Contents
