
Problem Statement
In this problem, you are provided with an array, nums
, comprising unique integers that are pre-sorted in ascending order. The task requires generating a list of string representations of sequential number ranges that collectively include every number in the array without any overlap or omissions.
A range [a, b]
means that it includes all integers from a
to b
inclusively. The range should be represented as "a->b" if a
differs from b
or just "a" if both are the same. The goal is to determine the minimal number of such ranges that effectively represent all numbers in the array.
Examples
Example 1
Input:
nums = [0,1,2,4,5,7]
Output:
["0->2","4->5","7"]
Explanation:
The ranges are: [0,2] --> "0->2" [4,5] --> "4->5" [7,7] --> "7"
Example 2
Input:
nums = [0,2,3,4,6,8,9]
Output:
["0","2->4","6","8->9"]
Explanation:
The ranges are: [0,0] --> "0" [2,4] --> "2->4" [6,6] --> "6" [8,9] --> "8->9"
Constraints
0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
- All the values of
nums
are unique. nums
is sorted in ascending order.
Approach and Intuition
To derive the solution for forming the shortest list of range strings that cover all numbers exactly as specified in 'nums,' consider the following approach:
Initialization:
- Start with an empty list to store the final range strings.
- Initialize markers to note the beginning of a new range (
start
) as well as the current number being examined (prev
).
Iterative Range Detection:
- Traverse through each number in the list. For each number:
- If
prev + 1
is not equal to the current number, this indicates the end of a current range and the beginning of a new range. - Append the constructed range to the result array:
- If
start
is the same asprev
, simply use "start". - Otherwise, use "start->prev" to denote a range from
start
toprev
.
- If
- Update the
start
to the current number, resetting the current range.
- If
- Traverse through each number in the list. For each number:
Handling the Last Detected Range:
- After finishing the loop, ensure to append the last detected range to the result since it won't be added inside the loop.
Special Edge Cases:
- Directly handle the scenario when
nums
is empty to prevent any undefined behavior by checking its length initially.
- Directly handle the scenario when
Following this logical breakdown using pointers to manage active ranges, we can effectively group the numbers in minimal, non-overlapping, consecutive sequences satisfying the requirements.
Solutions
- C++
class Solution {
public:
vector<string> rangeSummary(vector<int>& inputArray) {
vector<string> result;
for (int j = 0; j < inputArray.size(); j++) {
int startNum = inputArray[j];
// Loop to find consecutive numbers sequence
while (j + 1 < inputArray.size() && inputArray[j] + 1 == inputArray[j + 1]) {
j++;
}
if (startNum != inputArray[j]) {
result.push_back(to_string(startNum) + "->" + to_string(inputArray[j]));
} else {
result.push_back(to_string(startNum));
}
}
return result;
}
};
The provided C++ code defines a solution to construct summary ranges from a given vector of integers. The function rangeSummary
within the Solution
class processes an input vector to concisely represent contiguous sequences. Here's how the code tackles the problem:
- Initialize an empty vector
result
to store the final sequence of ranges. - Iterate through the input vector using a for loop.
- Assign the current element of the vector to
startNum
. This variable marks the beginning of a potential sequence. - Use a nested while loop to identify continuous consecutive sequences by checking if two successive numbers differ by exactly one. If true, increment the index
j
to extend the current range. - At the end of the while loop, check if
startNum
is different from the current element pointed byj
. If they differ, it means a range has been identified and is thus added toresult
in the formatstartNum->currentNumber
. If not, the number stands alone and is added toresult
as a single element string. - Repeat the steps until the entire array has been processed.
- Return the vector containing all the summarized ranges.
This function directly processes the input array, utilizing a combination of simple arithmetic and vector operations to build the output. It efficiently groups consecutive numbers into ranges, thereby compressing the information into a more readable format.
- Java
class Solution {
public List<String> findRanges(int[] numbers) {
List<String> rangeList = new ArrayList<>();
for (int i = 0; i < numbers.length; i++) {
int begin = numbers[i];
// Loop to find consecutive integers.
while (i + 1 < numbers.length && numbers[i] + 1 == numbers[i + 1]) {
i++;
}
if (begin != numbers[i]) {
rangeList.add(begin + "->" + numbers[i]);
} else {
rangeList.add(String.valueOf(begin));
}
}
return rangeList;
}
}
The given Java code solves the problem of finding and summarizing consecutive ranges in an array of integers. Here's how the code functions:
- Initialize an ArrayList named
rangeList
to store the resulting ranges as strings. - Traverse through the array of numbers using a for loop. For each number, check if it starts a new range by comparing it to the next number in the array.
- If the current number and the next one are consecutive, use a while loop to continue to the end of this consecutive sequence.
- Check if the range consists of more than one number:
- If so, format the range as
"begin->end"
and add torangeList
. - If the current number does not have any consecutive followers, add it directly as a string to
rangeList
.
- If so, format the range as
- Finally, return the
rangeList
.
This approach ensures each number or consecutive range is correctly identified and formatted, leveraging loop control and list operations efficiently.
- Python
class Solution:
def collateIntervals(self, numbers: List[int]) -> List[str]:
collected_ranges = []
index = 0
while index < len(numbers):
start_point = numbers[index]
while index + 1 < len(numbers) and numbers[index] + 1 == numbers[index + 1]:
index += 1
if start_point != numbers[index]:
collected_ranges.append(f"{start_point}->{numbers[index]}")
else:
collected_ranges.append(str(numbers[index]))
index += 1
return collected_ranges
In the provided Python program, you process a list of integers to generate a list of summary ranges. Here's a breakdown of how this solution operates:
- A list named
collected_ranges
is initialized to store the resulting summary ranges as strings. - You initialize
index
to zero to traverse through the list,numbers
. - A while loop runs as long as
index
is less than the length of the list. Inside this loop:- You set the
start_point
to the current number at the positionindex
. - Another while loop checks if the current number is sequentially followed by the next number (i.e., current number + 1 equals the next number). If true,
index
is incremented to extend the current range. - After determining the end of a range, you compare
start_point
with the current number atindex
. If they are different, it implies a range which is then appended tocollected_ranges
in the format "start->end". If they are the same, only a single number is appended as a string. index
is incremented to move to the next potential range or number.
- You set the
Final output, collected_ranges
, is a list of strings, each representing either a single number or a range of numbers in your input list. This allows you to clearly identify which numbers or sequences follow directly after one another.
No comments yet.