228. Summary Ranges - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given a sorted integer array nums without duplicates. Your task is to return a summary of its ranges as a list of strings. A range is defined as a sequence of consecutive numbers. For a continuous sequence, you should output "start->end", and if there is only one number, output it as a single string.

Example 1:

Input: nums = [0, 1, 2, 4, 5, 7]
Output: ["0->2", "4->5", "7"]
Explanation:
The continuous range [0, 1, 2] is summarized as "0->2", [4, 5] is summarized as "4->5", and the standalone number 7 is output as "7".

Example 2:

Input: nums = [0, 2, 3, 4, 6, 8, 9]
Output: ["0", "2->4", "6", "8->9"]
Explanation:
The single number 0 is output as "0", the continuous range [2, 3, 4] is output as "2->4", the single number 6 is output as "6", and the continuous range [8, 9] is output as "8->9".

Constraints:

0 ≤ nums.length ≤ 20
-2³¹ ≤ nums[i] ≤ 2³¹ - 1
All the values of nums are unique.
nums is sorted in ascending order.

Hints

Hint 1:
Since the array is sorted and contains no duplicates, you can iterate through it and identify consecutive sequences by checking if the current number plus one equals the next number.
Hint 2:
Maintain a pointer (or index) for the start of a range. When you detect a break in consecutiveness, you can form a range string from the start index to the previous index.
Hint 3:
Don’t forget to handle edge cases such as an empty array or when the final range reaches the end of the array.

Approaches

Approach 1: One-Pass Iteration Using Two Pointers

Idea:
Iterate through the array using an index variable. Keep track of the start of the current range. For each element, check if it is consecutive with the previous element. If not, finalize the current range:
- If the start and the current element are the same, add it as a single number.
- Otherwise, add the range in the format "start->end".
Process:
1. Initialize a variable start to the first index.
2. Iterate through the array; when a break in the consecutive sequence is found (or at the end of the array), generate the corresponding summary string.
3. Reset the start pointer for the next range.
Benefits:
This method requires only one pass through the array and uses constant extra space (aside from the output).

Code Implementations

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
The algorithm iterates through the array once, resulting in O(n) time complexity, where n is the length of nums.
Space Complexity:
Excluding the output, the algorithm uses O(1) extra space.

Step-by-Step Walkthrough

Initialization:
- Start with index i = 0 and an empty list for result.
- Set start = nums[0] as the beginning of the current range.
Iterate and Expand Range:
- For each index, check if the next element is exactly one greater than the current element.
- Continue moving i until the consecutive sequence ends.
Finalize the Range:
- If start equals the current number (end), add start as a string.
- Otherwise, add the range as "start->end".
Reset and Continue:
- Increment i to process the next potential range.
- Continue until the end of the array is reached.
Return the Result:
- Output the list of summarized ranges.

Visual Example

Consider nums = [0, 1, 2, 4, 5, 7]:

Iteration 1:
- Start at index 0: start = 0.
- Index 1: 0 + 1 = 1 (consecutive).
- Index 2: 1 + 1 = 2 (consecutive).
- Index 3: 2 + 1 ≠ 4 (break here).
  → Range: "0->2" is added.
Iteration 2:
- Start at index 3: start = 4.
- Index 4: 4 + 1 = 5 (consecutive).
- Index 5: 5 + 1 ≠ 7 (break).
  → Range: "4->5" is added.
Iteration 3:
- At index 5: single number 7 → "7" is added.

Final output: ["0->2", "4->5", "7"].

Common Mistakes

Not Handling Single-Element Ranges:
Always check if the start and end of a range are the same. In that case, output only the number rather than a range.
Off-by-One Errors:
Make sure to correctly update the pointer when the consecutive sequence ends.

Edge Cases

Empty Array:
If nums is empty, return an empty list.
Single Element Array:
The result should simply be a list containing that one element as a string.
No Consecutive Elements:
Each number will be output as an individual string.

Merging Intervals:
Similar ideas are used when merging overlapping intervals.
Range Summaries in Unsorted Arrays:
If the array wasn’t sorted, you would need to sort it first (which changes the complexity).

Merge Intervals
Insert Interval
Non-overlapping Intervals