Summary Ranges

EASY

Description

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
-2³¹ <= nums[i] <= 2³¹ - 1
All the values of nums are unique.
nums is sorted in ascending order.

Approaches

Checkout 2 different approaches to solve Summary Ranges. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

Iterate through the array and check each element with its next element to find ranges.

Algorithm

Initialize an empty result list
For each number in the array:
- Store the current number as start
- While next number is consecutive, increment index
- When non-consecutive number found or end reached:
  - If start equals current number, add single number
  - Else add range "start->current"

In this approach, we iterate through the array and for each element, we check if the next element is consecutive (current + 1). If it is consecutive, we continue until we find a non-consecutive element. When we find a non-consecutive element or reach the end of the array, we add the range to our result list.

public List<String> summaryRanges(int[] nums) {
    List<String> result = new ArrayList<>();
    if (nums == null || nums.length == 0) return result;
    
    for (int i = 0; i < nums.length; i++) {
        int start = nums[i];
        
        // Keep iterating while we find consecutive numbers
        while (i + 1 < nums.length && nums[i] + 1 == nums[i + 1]) {
            i++;
        }
        
        // Add range to result
        if (start != nums[i]) {
            result.add(start + "->" + nums[i]);
        } else {
            result.add(String.valueOf(start));
        }
    }
    
    return result;
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the input array as we need to traverse each element onceSpace Complexity: O(1) excluding the space required for output

Pros and Cons

Pros:

Simple and straightforward implementation
Easy to understand
No extra space required except for output

Cons:

Not optimized for very large arrays
Requires careful handling of integer overflow cases

Code Solutions

Checking out 4 solutions in different languages for Summary Ranges. Click on different languages to view the code.

public class Solution {
    public IList < string > SummaryRanges(int[] nums) {
        var ans = new List < string > ();
        for (int i = 0, j = 0, n = nums.Length; i < n; i = j + 1) {
            j = i;
            while (j + 1 < n && nums[j + 1] == nums[j] + 1) {
                ++j;
            }
            ans.Add(f(nums, i, j));
        }
        return ans;
    }
    public string f(int[] nums, int i, int j) {
        return i == j ? nums[i].ToString() : string.Format("{0}->{1}", nums[i], nums[j]);
    }
}

Video Solution

Watch the video walkthrough for Summary Ranges

Data Structures:

Array

Companies:

Yandex |Netflix |VK |