Problem Statement

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

Examples

Example 1:

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

Explanation:
The range 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"

Different Approaches

1️⃣ Linear Traversal

Intuition:

Since the input array nums is sorted and contains unique integers, any run of consecutive numbers will appear as a contiguous subarray. We want to collapse each such run into a single range:

• If a run has only one number x, we output “x”.
• If a run goes from a to b (a < b), we output "a->b".

By scanning left to right, we can detect where each consecutive run breaks (i.e., nums[i] ≠ num[i - 1] + 1), emit the previous run as a range, and then start a new run.

Approach:

1. Edge cases
   1. If nums is empty, return an empty result.
   2. If it has one element, return it as a single-element range.
2. Single-pass scan
   1. Initialize start = nums[0], marking the beginning of the current run.
   2. For each i from 1 to nums.size()-1:
      1. If nums[i] is not nums[i-1] + 1, then the run [start…nums[i-1]] ends at i-1.
         1. Emit "start" if start == nums[i-1], else "start->nums[i-1]".
         2. Set start = nums[i] to begin a new run.
   3. After the loop, emit the final run [start…nums.back()] using the same logic.

Code:

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        int n = nums.size();
        
        // Edge case: empty input
        if (n == 0) {
            return ans;
        }
        // Edge case: single element
        if (n == 1) {
            ans.push_back(to_string(nums[0]));
            return ans;
        }

        // 'start' marks the beginning of the current range
        int start = nums[0];

        // Scan from the second element to the end
        for (int i = 1; i < n; i++) {
            // Check if the current value breaks the consecutive run
            if (nums[i] != nums[i - 1] + 1) {
                // Emit the previous run [start…nums[i-1]]
                if (start == nums[i - 1]) {
                    // Single-element run
                    ans.push_back(to_string(start));
                } else {
                    // Multi-element run
                    ans.push_back(
                        to_string(start) + "->" + to_string(nums[i - 1])
                    );
                }
                // Begin a new run at nums[i]
                start = nums[i];
            }
        }

        // Emit the final run [start…nums.back()]
        if (start == nums.back()) {
            ans.push_back(to_string(start));
        } else {
            ans.push_back(
                to_string(start) + "->" + to_string(nums.back())
            );
        }

        return ans;
    }
};

Complexity Analysis:

• Time Complexity:O(n), where n is the size of the input array.
• Space Complexity:O(1)