Summary Ranges

XXX. Summary Ranges

Array

Interval

Problem Statement:

Given a sorted unique integer array nums, return the smallest sorted list of ranges that cover all the numbers in the array exactly. A range [a,b] is represented as: "a->b" if a != b, and "a" if a == b.

Example:

Input: [0, 1, 2, 4, 5, 7] Output: ["0->2", "4->5", "7"] Explanation: Ranges 0->2 and 4->5 represent consecutive integers. 7 is a single element.

Approach:

1. Initialize two pointers, i and j, to iterate over the array.
2. Move j forward as long as the next number is consecutive (nums[j] + 1 == nums[j+1]).
3. Once a non-consecutive element is found, add the range "nums[i]->nums[j]" or single element "nums[j]" to the result.
4. Repeat until the end of the array is reached.

Algorithm Intuition:

The algorithm works by identifying contiguous segments of numbers in the array using two pointers. It groups numbers into ranges whenever they are consecutive and adds these ranges to the result. Single numbers are treated as ranges with the same start and end.

Complexity:

Time Complexity: O(n), where n is the length of the array. The algorithm performs a single pass through the array.
Space Complexity: O(1), ignoring the space required for the output list.

Java Implementation:

// Two-pointer approach to summarize ranges in a sorted array
public List summaryRanges(int[] nums) {
    int i = 0, j = 0;
    List intervals = new ArrayList<>();

    // Iterate through the array
    while (j < nums.length) {
        // Move the end pointer (j) if the next number is consecutive
        while (j != nums.length - 1 && nums[j] + 1 == nums[j + 1]) 
            j++;

        // Add the range or single element to the intervals
        addInterval(nums[i], nums[j], intervals, i != j);

        // Move the start pointer (i) to the next position
        i = ++j;
    }

    return intervals;
}

// Helper method to format and add the range to the result
public void addInterval(Integer start, Integer end, List intervals, boolean range) {
    // If it's a range, format as "start->end"; otherwise, just the single number
    String s = range ? start.toString() + "->" + end.toString() : end.toString();
    intervals.add(s);
}