Jobs

Interviews

Discussions

Summary Ranges

Easy

Netflix

11 views

Topics:

ArraysStringsTwo Pointers

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.

Summary Ranges

Easy

Netflix

11 views

Topics:

ArraysStringsTwo Pointers

You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

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.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of integer values in the input array, and are negative numbers allowed?
What should I return if the input array is empty?
Is the input array guaranteed to be sorted in ascending order, and are there any duplicate values?
Can you provide examples of the expected output format for various input scenarios, especially edge cases like single-element arrays or arrays with only consecutive numbers?
Are there any memory constraints I should be aware of, given the potential size of the input array?

Brute Force Solution

Approach

The brute force approach to finding summary ranges involves examining every possible grouping of consecutive numbers. We essentially check each possible start and end point for a range. It's like trying every single combination to see which ones work.

Here's how the algorithm would work step-by-step:

Start by considering the first number by itself; this is a possible range.
Then, see if the first and second numbers together form a continuous range.
Continue adding numbers to this range one by one, checking if they're consecutive.
Once you find a range that's not consecutive, or you reach the end of the numbers, record the summary of that range.
Now, start over from the second number and repeat the same process of expanding the range and checking for consecutiveness.
Keep repeating this, starting from each number in the original set, until you've explored all possible starting points for ranges.
Finally, combine all the valid summary ranges you found.

Code Implementation

def summary_ranges_brute_force(numbers):
    result = []
    number_of_elements = len(numbers)

    for start_index in range(number_of_elements):
        current_range = [numbers[start_index]]
        end_index = start_index

        # Iterate through the remaining elements to extend the range.
        while end_index + 1 < number_of_elements and \
                numbers[end_index + 1] == numbers[end_index] + 1:
            end_index += 1
            current_range.append(numbers[end_index])

        # Append the summary range to the result.
        if len(current_range) > 1:
            result.append(str(current_range[0]) + "->" + str(current_range[-1]))
        else:
            result.append(str(current_range[0]))

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array nums of size n. For each number, it attempts to build a consecutive range. In the worst-case scenario, for each starting number, it might need to traverse a significant portion of the remaining array to check for consecutive numbers. Specifically, for the first element, it potentially iterates up to n-1 times to find the longest consecutive range starting from the first element. For the second element, it may iterate up to n-2 times, and so on. Therefore, the total number of operations can be approximated as (n-1) + (n-2) + ... + 1, which is equivalent to n*(n-1)/2. This simplifies to (n² - n)/2. Removing lower order terms and constants, the time complexity is O(n²).

Space Complexity

O(1) – The plain English explanation describes iterating through the list and building potential groups. The key operation is checking if the next number is consecutive. It does not describe the creation of any auxiliary data structures like lists, arrays, or hash maps to store intermediate results or track visited elements. The algorithm described keeps track of the start and end of the range using a fixed number of variables and appends the result when a range ends. Therefore, the space complexity is constant, independent of the input size N.

Optimal Solution

Approach

The goal is to find continuous ranges of numbers in a list and represent them concisely. The efficient solution walks through the list once, identifying range boundaries as it goes. It avoids unnecessary revisits or comparisons, making it faster.

Here's how the algorithm would work step-by-step:

Start at the beginning of the list of numbers.
Consider the current number as the possible start of a range.
Look at the next number to see if it continues the range (is one bigger than the current number).
Keep checking subsequent numbers to see if the range continues.
If a number doesn't continue the range, then the previous number was the end of the range.
If the range consists of only one number, record that single number.
If the range consists of multiple numbers, record the start and end numbers of the range with an arrow in between.
Start a new range from the number that broke the previous range.
Repeat this process until you reach the end of the list of numbers.

Code Implementation

def summary_ranges(numbers):
    ranges = []
    if not numbers:
        return ranges

    start_range = numbers[0]
    end_range = numbers[0]

    for i in range(1, len(numbers)):
        current_number = numbers[i]

        # Check if the current number continues the range
        if current_number == end_range + 1:
            end_range = current_number
        else:
            # The current number breaks the range, so save the previous range
            if start_range == end_range:
                ranges.append(str(start_range))
            else:
                ranges.append(str(start_range) + "->" + str(end_range))

            # Start a new range from the current number
            start_range = current_number
            end_range = current_number

    # Add the last range
    if start_range == end_range:
        ranges.append(str(start_range))
    else:
        # Add the last range
        ranges.append(str(start_range) + "->" + str(end_range))

    return ranges

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n once. Inside the loop, there is a while loop that extends the range as long as consecutive numbers are found. However, each number is visited at most twice: once by the outer loop and at most once by the inner while loop to extend the range. Therefore, the time complexity is directly proportional to the number of elements in the input array, making it O(n).

Space Complexity

O(1) – The algorithm's space complexity is determined by the extra space it uses beyond the input array. In this case, we primarily need to store a few variables: the start of the current range, potentially the end of the range, and a results list. However, even if all ranges consist of only one element, the number of ranges is bounded by the number of elements in the input array, N. The results list stores strings. While the number of strings can be N in the worst case, each string's size is relatively small, representing a range or a single number. The extra space needed for these variables is independent of the input array's size, so the auxiliary space used by the algorithm is constant. Specifically, we do not create auxiliary data structures that scale with the input size N. The results list only grows to the size of the number of range outputs, where the maximum number of outputs will never exceed N. The space used for this list is constant. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list to avoid NullPointerException or unexpected behavior.
Input array with a single element	Return a list containing the single element as a string.
Input array with two consecutive elements	Check if the elements form a range and format the output accordingly.
Input array with a long sequence of consecutive numbers	Ensure the algorithm efficiently identifies and summarizes long ranges without excessive iteration.
Input array with negative numbers, including a sequence of consecutive negative numbers	The algorithm should correctly handle negative numbers and their ranges.
Input array with very large integers close to the maximum integer value	The algorithm should avoid integer overflow when checking for consecutive numbers.
Input array with a mix of small, large, positive, and negative integers	The algorithm should handle the diverse number distribution without issue.
Integer overflow when forming the range strings	Convert integers to long to prevent overflow during range calculations and string construction if necessary.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of integer values in the input array, and are negative numbers allowed?
What should I return if the input array is empty?
Is the input array guaranteed to be sorted in ascending order, and are there any duplicate values?
Can you provide examples of the expected output format for various input scenarios, especially edge cases like single-element arrays or arrays with only consecutive numbers?
Are there any memory constraints I should be aware of, given the potential size of the input array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the first number by itself; this is a possible range.
Then, see if the first and second numbers together form a continuous range.
Continue adding numbers to this range one by one, checking if they're consecutive.
Once you find a range that's not consecutive, or you reach the end of the numbers, record the summary of that range.
Now, start over from the second number and repeat the same process of expanding the range and checking for consecutiveness.
Keep repeating this, starting from each number in the original set, until you've explored all possible starting points for ranges.
Finally, combine all the valid summary ranges you found.

Code Implementation

def summary_ranges_brute_force(numbers):
    result = []
    number_of_elements = len(numbers)

    for start_index in range(number_of_elements):
        current_range = [numbers[start_index]]
        end_index = start_index

        # Iterate through the remaining elements to extend the range.
        while end_index + 1 < number_of_elements and \
                numbers[end_index + 1] == numbers[end_index] + 1:
            end_index += 1
            current_range.append(numbers[end_index])

        # Append the summary range to the result.
        if len(current_range) > 1:
            result.append(str(current_range[0]) + "->" + str(current_range[-1]))
        else:
            result.append(str(current_range[0]))

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the list of numbers.
Consider the current number as the possible start of a range.
Look at the next number to see if it continues the range (is one bigger than the current number).
Keep checking subsequent numbers to see if the range continues.
If a number doesn't continue the range, then the previous number was the end of the range.
If the range consists of only one number, record that single number.
If the range consists of multiple numbers, record the start and end numbers of the range with an arrow in between.
Start a new range from the number that broke the previous range.
Repeat this process until you reach the end of the list of numbers.

Code Implementation

def summary_ranges(numbers):
    ranges = []
    if not numbers:
        return ranges

    start_range = numbers[0]
    end_range = numbers[0]

    for i in range(1, len(numbers)):
        current_number = numbers[i]

        # Check if the current number continues the range
        if current_number == end_range + 1:
            end_range = current_number
        else:
            # The current number breaks the range, so save the previous range
            if start_range == end_range:
                ranges.append(str(start_range))
            else:
                ranges.append(str(start_range) + "->" + str(end_range))

            # Start a new range from the current number
            start_range = current_number
            end_range = current_number

    # Add the last range
    if start_range == end_range:
        ranges.append(str(start_range))
    else:
        # Add the last range
        ranges.append(str(start_range) + "->" + str(end_range))

    return ranges

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list to avoid NullPointerException or unexpected behavior.
Input array with a single element	Return a list containing the single element as a string.
Input array with two consecutive elements	Check if the elements form a range and format the output accordingly.
Input array with a long sequence of consecutive numbers	Ensure the algorithm efficiently identifies and summarizes long ranges without excessive iteration.
Input array with negative numbers, including a sequence of consecutive negative numbers	The algorithm should correctly handle negative numbers and their ranges.
Input array with very large integers close to the maximum integer value	The algorithm should avoid integer overflow when checking for consecutive numbers.
Input array with a mix of small, large, positive, and negative integers	The algorithm should handle the diverse number distribution without issue.
Integer overflow when forming the range strings	Convert integers to long to prevent overflow during range calculations and string construction if necessary.