Summary Ranges - LeetCode 228 Solution

Problem Overview

#

The Summary Ranges problem from LeetCode asks you to create a list of consecutive ranges as strings.

Problem Statement: You are given a sorted unique integer array nums. 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 result should be formatted as:

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

Example:

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

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

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

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

Solution Approach

#

C# Solution - Single Pass with Break Detection

#

Use a single variable start to track the beginning of a range and iterate through the array. When a break in consecutiveness is found (when current element is not exactly previous + 1), format and add the previous range to the result. Handle the formatting based on whether it’s a single element or a range. Add the final range after the loop completes.

public class Solution {
    public IList<string> SummaryRanges(int[] nums) {
        var ranges = new List<string>();

        if(nums.Length == 0) {
            return ranges;
        }

        var start = nums[0];

        for(int i = 1; i < nums.Length; i++) {
            if(nums[i] != nums[i - 1] + 1){
                if(start == nums[i - 1]){
                    ranges.Add(start.ToString());
                }else{
                    ranges.Add($"{start}->{nums[i - 1]}");
                }
                start = nums[i];
            }
        }

        if(start == nums[nums.Length - 1]){
            ranges.Add(start.ToString());
        }else {
            ranges.Add($"{start}->{nums[nums.Length - 1]}");
        }

        return ranges;
    }
}

Time Complexity: O(n) - single pass through the array Space Complexity: O(1) - excluding output, only constant extra space for variables

Key Insights

#

1. Range Start Tracking: Use a single variable to mark the start of each consecutive range
2. Break Detection: Detect breaks by checking if nums[i] != nums[i-1] + 1
3. Formatting Logic: Format as single number if start equals end, otherwise use “start->end” format
4. Two Formatting Points: Handle range formatting both when a break occurs and after the loop
5. Final Range Handling: Ensure the last range is added after the loop completes
6. Empty Array Edge Case: Return empty list immediately for empty input arrays

Related Problems

#

• Missing Ranges
• Data Stream as Disjoint Intervals
• Merge Intervals

Video Tutorial

#

Watch the complete explanation and walkthrough in the video above for a detailed solution approach and implementation details.