The Summary Ranges problem asks us to take a sorted list of integers and group consecutive numbers into ranges. For example, given the input [0, 1, 2, 4, 5, 7], the output would be [“0->2”, “4->5”, “7”]. The goal is to find and summarize sequences of consecutive numbers in a clean and structured format.
Imagine you’re analyzing a timeline and want to condense periods of activity into summaries, instead of listing every single point in time.
Optimal Approach
Algorithm Pattern: Linear Traversal
Data Structure: ArrayList
• The algorithm follows the linear traversal pattern, which processes an array in a single pass, leveraging the sequential order of the input to minimize complexity.
• Why linear traversal works:
• The input array is sorted, so consecutive elements naturally form ranges.
• By iterating once, the algorithm efficiently identifies range boundaries.
• Why ArrayList is suitable:
• It provides dynamic resizing to accommodate varying numbers of ranges.
• It allows appending strings in O(1) amortized time.
Steps of the Algorithm
1. Initialize a list to store results.
2. Use two pointers to track the start and end of a range.
3. Iterate through the array:
• If the current number is not consecutive to the previous, close the range and start a new one.
4. Add the final range after the loop.
5. Return the result list.
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result; // Handle empty input
int start = nums[0];
for (int i = 1; i <= nums.length; i++) {
if (i == nums.length || nums[i] != nums[i - 1] + 1) {
if (start != nums[i - 1]) {
result.add(start + "->" + nums[i - 1]);
} else {
result.add(String.valueOf(start));
}
if (i < nums.length) start = nums[i];
}
}
return result;
}
}Step 1: Setting Up the Result List
List<String> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result; // Handle empty input
- Initializes a list to store the summarized ranges.
- Handles edge case where there is no input by returning early.
- This ensures function does not break for empty input and provides a clean slate to store results.
Step 2: Initialize the First Activity Start Time
int start = nums[0];- Sets the first number as the start of the first range
- The algorithm needs to track the beginning of each new range
- You need to track where each range begins to summarize the activity correctly.
Step 3: Iterate Over The Data
for(int i = 1; i <= nums.length; i++) {- Iterate through the array, including an additional iteration for finalizing the last range.
Step 4: Check Range Continuity
if(i == nums.length || nums[i] != nums[i - 1] + 1) {- Checks whether the current number ends a range or if the loop has reached the end of the array.
- Efficient for sorted arrays but assumes no duplicates.
Step 5: Add Range To Result
if (start != nums[i - 1]) {
result.add(start + "->" + nums[i - 1]);
} else {
result.add(String.valueOf(start));
}- Adds the completed range to the result list. If the range contains only one number, it adds that number as a standalone string.
Step 6: Start a New Range
if(i < nums.length) {
start = nums[i];
}- Updates the start to the current element for the next range.
Step 7: Return
return result;- This completes the function by providing the final summarized data.
Why the Code Was Written This Way
• Efficient Processing: The single loop processes the array in O(n) time, making it fast for large datasets.
• Clean Range Summarization: Using start and conditional checks ensures clear and concise range formation without redundant logic.
• Handles Edge Cases: Extending the loop to one past the array length and checking conditions like nums.length == 0 ensures the solution works for all input sizes.
This approach is straightforward, leveraging the sorted nature of the input data and avoiding unnecessary space usage beyond the result list. It mirrors the steps you’d take to summarize web analytics data accurately and efficiently.
