228. Summary Ranges

https://leetcode.com/problems/summary-ranges/description/?envType=study-plan-v2&envId=top-interview-150

Easy:

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.

Approach :

1. Initialization: Start by iterating over the array. Maintain two pointers or variables:

   • start to track the beginning of a potential range.

   • end to determine the end of the current contiguous range.

2. Iteration:

   • Traverse through the array and check if the current number is consecutive to the previous one.

   • If it is not consecutive, close the current range and start a new one.

3. Range Formatting:

   • If start == end, the range consists of a single number.

   • Otherwise, format it as start->end.

4. Edge Cases:

   • Handle empty arrays.

   • Handle arrays with only one element.

---

Algorithm Steps :

1. Initialize start to the first element of nums.

2. Iterate through nums:

   • If a gap between nums[i] and nums[i-1] exists, record the range [start, nums[i-1]] and reset start to nums[i].

3. At the end of the loop, add the final range.

4. Return the formatted ranges.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        if (nums.length == 0) return result;

        int start = nums[0];
        for (int i = 1; i <= nums.length; i++) {
            if (i == nums.length || nums[i] != nums[i - 1] + 1) {
                if (start == nums[i - 1]) {
                    result.add(String.valueOf(start));
                } else {
                    result.add(start + "->" + nums[i - 1]);
                }
                if (i < nums.length) start = nums[i];
            }
        }
        return result;
    }
}