Solving the "Summary Ranges" Problem

In this article, we will explore a common coding problem known as Summary Ranges, where the goal is to condense consecutive numbers from a sorted array into a readable list of ranges.

Problem Statement

You are given a sorted, unique integer array nums. The objective is to return the smallest list of ranges that covers all the numbers in the array. Each range [a, b] is defined as a set of consecutive numbers, where:

• If a != b, output the range as "a->b".
• If a == b, output the single number as "a".

Example 1:

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

Output: ["0->2", "4->5", "7"]

Explanation:

• The first range [0, 1, 2] is represented as "0->2".
• The second range [4, 5] is represented as "4->5".
• The single number 7 is represented as "7".

Example 2:

Input: nums = [0, 2, 3, 4, 6, 8, 9]

Output: ["0", "2->4", "6", "8->9"]

Explanation:

• The first number 0 is a single number, so it's output as "0".
• The second range [2, 3, 4] is represented as "2->4".
• The number 6 is represented as "6".
• The range [8, 9] is represented as "8->9".

Approach

We will break down the problem step by step to understand how to solve it efficiently.

1. Initialize the result list: We need a list to store the final ranges.
2. Loop through the list: We iterate through the numbers in the nums array.
3. Track consecutive numbers: We check if consecutive numbers exist and group them together.
4. Handle ranges and single numbers: If a group contains more than one number, it's a range. If it's a single number, we store it as is.
5. Store the results: We append the identified ranges or individual numbers to the result list.

Python Implementation

Detailed Explanation

Let’s walk through how this solution works with the example nums = [0, 1, 2, 4, 5, 7]:

1. Initialization: We start with an empty list result to store the output and an index variable i = 0.
2. Outer Loop: The loop runs while i is less than the length of the nums array. At each step, we identify a potential range:
3. Inner Loop for Consecutive Numbers: We check if the next number is consecutive to the current number. If it is, we increment i to keep expanding the range. In our example:
4. Adding to Result: After processing the consecutive numbers, we check:
5. Continue: We move i to the next number that doesn’t belong to the current range and repeat the process.
6. Handling Single Numbers: If a number doesn’t have any consecutive numbers (like 7 in our example), we add it directly to the result list as a single number.

Time Complexity

This solution iterates through the list once, making it O(n), where n is the length of the nums array. Given the constraint that the array is sorted, this is an efficient approach to the problem.

Example Walkthrough

Let’s walk through the input nums = [0, 1, 2, 4, 5, 7]:

1. Start at 0. The next numbers 1 and 2 are consecutive.
2. The range "0->2" is added to the result.
3. Move to 4. The next number 5 is consecutive.
4. The range "4->5" is added to the result.
5. Move to 7, which is a single number, so "7" is added to the result.

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

Conclusion

The Summary Ranges problem is an interesting challenge that tests our ability to work with arrays and ranges efficiently. By breaking down the problem into consecutive ranges, we can produce the desired output in an optimal way. This approach is both readable and efficient for small to medium-sized arrays.