Find the Start and End Number of Continuous Ranges

Medium

Asked by:

9 views

Topics:

ArraysTwo Pointers

You are given a sorted list of unique integers nums. You are tasked with finding the smallest sorted list of ranges that exactly covers all the numbers in the list. That is, each element in nums must be covered by 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

Return the minimal list of ranges that covers all the numbers in the list.

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"

Example 3:

Input: nums = []
Output: []

Example 4:

Input: nums = [-1]
Output: ["-1"]

Example 5:

Input: nums = [0]
Output: ["0"]

Constraints:

0 <= nums.length <= 100
-10⁹ <= nums[i] <= 10⁹
All values in nums are unique.
nums is sorted in ascending order.

Try coding it in LeetCode

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 range of possible integer values within the input array?
What should I return if the input array is null or empty?
Are the integers in the input array guaranteed to be sorted in ascending order?
Can the input array contain duplicate numbers, and if so, how should I handle them in the ranges?
Is there a specific format required for the output list of strings (e.g., can I use any separator besides "->" if the start and end are different)?

Brute Force Solution

Approach

The brute force approach to finding continuous ranges in a list of numbers involves checking every possible starting point and then extending that range as far as possible. We explore all combinations to identify the continuous sequences. It's like looking at every possibility, one at a time.

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

Start by looking at the first number in the list.
See if the next number is one greater than the current number. If it is, keep going; we're in a range!
Keep extending this range as long as the numbers continue to increase by one each time.
Once the numbers stop being consecutive, this range is over.
Write down the start and end of that range.
Now, start again from the next number in the list, even if it was part of a previous range, and repeat the process.
Continue this until you've checked every single number in the list as a potential start of a range.
At the end, you'll have a list of all the continuous ranges you found.

Code Implementation

def find_ranges_brute_force(numbers):
    ranges = []
    list_length = len(numbers)

    for start_index in range(list_length):
        current_number = numbers[start_index]
        end_index = start_index

        # Attempt to extend the range
        while end_index + 1 < list_length and numbers[end_index + 1] == current_number + 1:

            end_index += 1
            current_number += 1

        # If range contains more than one element, record it
        if end_index > start_index:

            ranges.append([numbers[start_index], numbers[end_index]])

    return ranges

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through each of the n numbers in the input list as a potential starting point for a continuous range. For each starting number, the algorithm potentially iterates through the remaining numbers in the list to extend the range as far as possible. In the worst case, for each of the n starting positions, we might have to examine up to n elements to determine the range. Therefore, the total number of operations can be approximated as n * n/2, resulting in a time complexity of O(n²).

Space Complexity

O(1) – The provided algorithm iterates through the input list and checks for continuous ranges without using any auxiliary data structures that scale with the input size. It only requires a few variables to keep track of the start and end of a range. These variables consume a constant amount of space, irrespective of the input list's size (N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to find consecutive number sequences within a given list. We can efficiently achieve this by iterating through the list and identifying the start and end of each continuous range. The overall idea is to identify when a sequence starts and stops.

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

Start by looking at the first number in the list. This is potentially the start of a range.
Check if the next number is one greater than the current number. If it is, we are still in the same continuous range.
Keep checking consecutive numbers to see if they continue the sequence, building the current range.
When you find a number that is not one greater than the previous number, you've reached the end of the current range.
Record the start and end of the range you just identified. The start is the first number of the sequence. The end is the last number before the discontinuity.
Start a new range with the number where the previous sequence ended.
Repeat these steps until you have processed all the numbers in the list.

Code Implementation

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

    start_of_range = numbers[0]
    end_of_range = numbers[0]

    for i in range(1, len(numbers)):
        # Check if the current number continues the range
        if numbers[i] == numbers[i - 1] + 1:
            end_of_range = numbers[i]
        else:
            # The current number does not continue the range.
            ranges.append([start_of_range, end_of_range])
            start_of_range = numbers[i]
            end_of_range = numbers[i]

    # Add the last range to result list
    ranges.append([start_of_range, end_of_range])

    return ranges

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list of numbers once. In each iteration, it performs a constant amount of work, checking if the next number continues the current range. The number of iterations is directly proportional to the number of elements, n, in the input list. Therefore, the time complexity is O(n).

Space Complexity

O(R) – The algorithm's space complexity is determined by the space needed to store the ranges. In the worst-case scenario, where no numbers are consecutive, the number of ranges R would be equal to the number of input elements N. Therefore, we need to store R ranges (start and end points for each), and the space grows linearly with the number of ranges found. In the most efficient case, where all the numbers are in sequence, the amount of space used is O(1) since we are only storing one range. Thus we can say that we are storing R ranges, giving O(R).

Edge Cases

Case	How to Handle
Empty or null input array	Return an empty list if the input array is null or has a length of zero.
Array with one element	Return a list containing a single string representing that element.
Array with two elements that are consecutive	Return a list containing a single string representing the range 'start->end'.
Array with two elements that are not consecutive	Return a list containing two strings, each representing a single element.
Array with all identical values	Iterate through the array and appropriately handle consecutive similar numbers.
Array with negative numbers, including extremely small negative numbers	The algorithm should correctly process the negative numbers without integer overflow.
Array with large positive numbers close to the maximum integer value	Ensure that adding 1 to a number doesn't cause an integer overflow that incorrectly identifies a range.
Array is very large, potentially exceeding memory limitations	The solution should use an iterative approach and not recursion, to avoid stack overflow errors, and process data in chunks if necessary to manage memory usage.

Empty or null input array

How to Handle:

Return an empty list if the input array is null or has a length of zero.

Array with one element

How to Handle:

Return a list containing a single string representing that element.

Array with two elements that are consecutive

How to Handle:

Return a list containing a single string representing the range 'start->end'.

Array with two elements that are not consecutive

How to Handle:

Return a list containing two strings, each representing a single element.

Array with all identical values

How to Handle:

Iterate through the array and appropriately handle consecutive similar numbers.

Array with negative numbers, including extremely small negative numbers

How to Handle:

The algorithm should correctly process the negative numbers without integer overflow.

Array with large positive numbers close to the maximum integer value

How to Handle:

Ensure that adding 1 to a number doesn't cause an integer overflow that incorrectly identifies a range.

Array is very large, potentially exceeding memory limitations

How to Handle:

The solution should use an iterative approach and not recursion, to avoid stack overflow errors, and process data in chunks if necessary to manage memory usage.