grid47 Exploring patterns and algorithms
Oct 15, 2024
5 min read
Solution to LeetCode 228: Summary Ranges Problem
You are given a sorted array of unique integers. Your task is to group consecutive numbers into ranges and return a sorted list of these ranges. A range [a,b] includes all integers from a to b (inclusive). Each range should be represented as ‘a->b’ if a != b or ‘a’ if a == b.
Problem
Approach
Steps
Complexity
Input: A sorted array of unique integers.
Example: Input: nums = [-3,-2,-1,1,2,5]
Constraints:
• The array length is in the range [0, 20].
• All values in the array are unique.
• The values are sorted in ascending order.
• Each integer lies in the range [-2^31, 2^31 - 1].
Output: A sorted list of ranges that cover all the numbers in the array exactly, with each range formatted as 'a->b' or 'a'.
Example: Output: ['-3->-1','1->2','5']
Constraints:
• Each number in the input array must be included in exactly one range.
• Ranges must not include any integers outside the input array.
Goal: Identify consecutive sequences of numbers and group them into ranges.
Steps:
• Initialize a pointer to traverse the array.
• For each element, determine the start of a range.
• Continue iterating until the end of the current range is reached (next number is not consecutive).
• Add the range to the result list in the appropriate format ('a->b' or 'a').
• Repeat until all elements are processed.
Goal: The problem is constrained as follows:
Steps:
• Input array length is at most 20.
• Values are sorted in ascending order.
• Each value is unique.
• Values lie within the 32-bit signed integer range.
Assumptions:
• The input array is non-null and adheres to the constraints.
• Consecutive values are integers differing by exactly 1.
Approach: The solution involves iterating through the array to identify consecutive sequences and recording them as ranges. A two-pointer technique can be used to determine the start and end of each range.
Observations:
• Consecutive numbers can be identified when the difference between adjacent elements is 1.
• A range can be represented compactly as 'a->b' or just 'a' if it contains a single number.
• Iterate through the array while tracking the start of each range.
• When a non-consecutive number is encountered, finalize the current range.
Steps:
• Initialize an empty result list and start iterating from the first element.
• For each element, track the beginning of the current range.
• Continue until the end of the range (next element is not consecutive).
• Add the range to the result list in the appropriate format.
• Repeat for all elements in the array.
Empty Inputs:
• An empty input array should return an empty result.
Large Inputs:
• The largest possible array of size 20 with mixed consecutive and non-consecutive elements.
Special Values:
• An array with all consecutive numbers.
• An array where no two numbers are consecutive.
Constraints:
• Ensure no ranges extend beyond the given numbers.
vector<string> summaryRanges(vector<int>& nums) {
constint size_n = nums.size();
vector<string> res;
if ( 0== size_n) return res;
for (int i =0; i < size_n;) {
int start = i, end = i;
while (end +1< size_n && nums[end+1] == nums[end] +1) end++;
if (end > start) res.push_back(to_string(nums[start]) +"->"+ to_string(nums[end]));
else res.push_back(to_string(nums[start]));
i = end+1;
}
return res;
}
1 : Function Definition
vector<string> summaryRanges(vector<int>& nums) {
Defines the function `summaryRanges` that takes a reference to a vector of integers and returns a vector of strings representing consecutive ranges.
2 : Variable Initialization
constint size_n = nums.size();
Gets the size of the input vector `nums` and stores it in `size_n` for later use.
3 : Result Container
vector<string> res;
Initializes an empty vector `res` to store the resulting summary ranges.
4 : Edge Case Check
if ( 0== size_n) return res;
Checks if the input vector is empty; if so, returns an empty result vector.
5 : Main Loop
for (int i =0; i < size_n;) {
Starts a loop to iterate over the elements of `nums`.
6 : Range Initialization
int start = i, end = i;
Initializes two variables `start` and `end` to the current index `i`. These will track the beginning and end of a consecutive range.
7 : Range Expansion
while (end +1< size_n && nums[end+1] == nums[end] +1) end++;
Expands the `end` pointer to include consecutive numbers in the range.
8 : Range Formatting
if (end > start) res.push_back(to_string(nums[start]) +"->"+ to_string(nums[end]));
If a range of consecutive numbers is found, adds the formatted range (e.g., 'start->end') to the result vector.
9 : Single Number Case
else res.push_back(to_string(nums[start]));
If no range is found (i.e., the number is isolated), adds the number as a single element string to the result.
10 : Advance Index
i = end+1;
Moves the index `i` to the next number after the current range.
11 : Return Result
return res;
Returns the vector `res`, which contains the summary of ranges as strings.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: Each element is visited exactly once.
Best Case: O(1)
Worst Case: O(1)
Description: No additional space is required beyond the result list.
