{x}
blog image

Summary Ranges

You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

  • "a->b" if a != b
  • "a" if a == b

 

Example 1:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

Example 2:

Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

 

Constraints:

  • 0 <= nums.length <= 20
  • -231 <= nums[i] <= 231 - 1
  • All the values of nums are unique.
  • nums is sorted in ascending order.

Solution Explanation: Summary Ranges

This problem asks to generate a list of strings representing the ranges of a sorted unique integer array. The goal is to represent consecutive numbers as a range (e.g., "1->3") and single numbers as themselves (e.g., "5").

Approach: Two Pointers

The most efficient approach uses two pointers, i and j, to track the start and end of a potential range.

  1. Initialization: i and j both start at index 0.
  2. Iteration: The outer loop iterates through the array using i.
  3. Range Detection (Inner Loop): The inner loop (using j) extends as long as consecutive numbers are found (nums[j+1] == nums[j] + 1). This efficiently identifies the end of a range.
  4. Range Formation: Once the inner loop finishes, a range is identified. The function f(i, j) constructs the string representation of this range:
    • If i == j (single element range), it returns the number as a string.
    • If i != j (multiple element range), it returns a string in the format "start->end".
  5. Pointer Update: After forming a range, i is updated to j + 1 to begin searching for the next range.
  6. Result: The process continues until i reaches the end of the array. The function returns a list containing all the generated range strings.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the input array. This is because we iterate through the array at most once using two pointers. The inner loop only adds a constant amount of work per element.
  • Space Complexity: O(1) in most implementations. The space used is relatively constant regardless of input size. Some implementations might use extra space proportional to the number of ranges found, but that's generally a small and bounded number (at most n). The dominant space use remains constant.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, C#)

The code examples in multiple programming languages demonstrate the two-pointer approach. Each example follows the same algorithm described above, varying only in syntax and language-specific functions. The helper function f(i, j) is consistently used to format the range string. These examples are well-commented for easy understanding.

Example Walkthrough (Python)

Let's trace the Python code with the input nums = [0,1,2,4,5,7]:

  1. i = 0, j = 0. Inner loop runs until j = 2 (nums[3] != nums[2] + 1).
  2. f(0, 2) returns "0->2". This is added to ans.
  3. i becomes 3.
  4. i = 3, j = 3. Inner loop runs until j = 4 (nums[5] != nums[4] + 1).
  5. f(3, 4) returns "4->5". This is added to ans.
  6. i becomes 5.
  7. i = 5, j = 5. Inner loop doesn't run.
  8. f(5, 5) returns "7". This is added to ans.
  9. i becomes 6, the loop terminates.
  10. ans is ["0->2", "4->5", "7"].

This clearly shows how the two-pointer approach efficiently identifies and represents the ranges within the sorted input array.