algoadvance

Given a sorted 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 list should be output as:

Clarifying Questions

  1. Does the array contain duplicates?
    • No, the array does not contain duplicate numbers as it is sorted and covers all the numbers exactly.
  2. Are there any constraints on the size of the input array?
    • The problem statement doesn’t specify the size constraints, so we should assume the general case.
  3. What to return if the array is empty?
    • If the array is empty, we should return an empty list.

Code

def summaryRanges(nums):
    ranges = []
    if not nums:
        return ranges

    start = nums[0]
    for i in range(1, len(nums)):
        # Check if the current number is not consecutive
        if nums[i] != nums[i-1] + 1:
            # If the start number is the same as the previous number
            if start == nums[i-1]:
                ranges.append(f"{start}")
            else:
                ranges.append(f"{start}->{nums[i-1]}")
            # Update the start to the current number
            start = nums[i]

    # Handle the last range
    if start == nums[-1]:
        ranges.append(f"{start}")
    else:
        ranges.append(f"{start}->{nums[-1]}")
    
    return ranges

# Example usage:
nums = [0,1,2,4,5,7]
print(summaryRanges(nums)) # Output: ["0->2", "4->5", "7"]

nums = [0,2,3,4,6,8,9]
print(summaryRanges(nums)) # Output: ["0", "2->4", "6", "8->9"]

Strategy

  1. Initialization: Create an empty list ranges to store the result.
  2. Edge Case: If the input list nums is empty, return the empty list.
  3. Iteration: Iterate through the list starting from the second element:
    • If the current element is not consecutive with the previous one, determine the range based on start and the previous number.
    • Append the determined range to the ranges list.
    • Update the start to the current number.
  4. Final Range: After the loop, ensure that the last number or range is added to the ranges list.
  5. Return the list of ranges.

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the number of elements in the input array nums. This is because we are iterating through the list once, performing constant-time operations within the loop.

Try our interview co-pilot at AlgoAdvance.com