Summary Ranges – 228. LeetCode

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 and Data Structure

• Algorithm Used: Single-pass traversal.

• Data Structure Used: A list to store results.

Intuition Behind the Algorithm

This is the optimal solution because it emphasizes minimal operations:

• Instead of iterating over gaps and managing extraneous checks, the algorithm directly builds ranges based on observed conditions.

• This is well-suited for the problem because the array is sorted, which guarantees that consecutive integers will appear next to each other.

1. Sorted Input Assumption: The problem specifies sorted input, which eliminates the need for additional sorting or complex data structures like heaps or trees.

2. Space Efficiency: No extra data structures (e.g., hash maps) are needed beyond the result list and a few variables.

3. Direct Range Formation: Using pointers for start and end minimizes unnecessary computations.

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.

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        if(nums.length == 0) return result;

        int start = nums[0];

        for(int i = 1; i <= nums.length; i++) {
            //If we reach the last element or the current element is not consecutive to previous element
            if(i == nums.length || nums[i] != nums[i - 1] + 1) {
                //If the start is equal to the previous element, it means the range contains only one number
                if(start == nums[i - 1]) {
                    result.add(String.valueOf(start));
                } else {
                    result.add(start + "->" + nums[i - 1]);
                }

                if(i < nums.length) {
                    start = nums[i];
                }
            }
        }
        return result;
    }
}

Step 1: Setting Up the Result List

List<String> result = new ArrayList<>();
if(nums.length == 0) return result;

• 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];

• Stores the start of the current range (or session).
• Prepares to track consecutive timestamps
• 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++) {

• A loop is needed to analyze all the time stamps and decide when to close a range.

Step 4: Check for End of a Range

if(i == nums.length || nums[i] != nums[i - 1] + 1) {

• Ends a range if:
  • You’ve reached the last timestamp
  • The current timestamp is not consecuitve to the previous one (nums[i] != nums[i – 1] + 1).
  • This identifies when a session should be summarized and stored.

Step 5: Summarize the Range

if(start == nums[i - 1]) {
    result.add(String.valueOf(start));
} else {
    result.add(start + "->" + nums[i - 1]);
}

• If the range has one timestamp, adds it as a single number.
• Otherwise, adds a formatted range string, combining the start and end of the session.
• Ensures that both single timestamps and ranges are handled correctly and added to the summary

Step 6: Start a New Range

if(i < nums.length) {
    start = nums[i];
}

• Updates the start to the current timestamp for the next range.
• Prepares for summarizing the next session.

Step 7: Return the Summary Report

return result;

• This completes the function by providing the final summarized activity 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.