Summary Ranges - Leetcode Solution

Problem statement: Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

Example:

Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99, Output: ["2", "4->49", "51->74", "76->99"]

Solution: To solve this problem, we can traverse through the array and keep track of the current number and its previous number. If the difference between the current number and the previous number is greater than or equal to two, then we have a missing range between them. We can add this missing range to a list. At the end of the traversal, we need to check if there is any remaining range after the last element of the array, and if so, we can add that range to the list.

Algorithm:

1. Create an empty list to store the missing ranges.
2. Initialize a variable to keep track of the previous element of the array.
3. Traverse through the array using a for loop: a. Check if the difference between the current element and the previous element is greater than or equal to two. b. If so, then add the missing range in the format "prev+1->curr-1" to the list. c. Update the previous element to the current element.
4. Check if there is any remaining range after the last element of the array. a. If so, add the remaining range in the format "prev+1->upper" to the list.
5. Return the list of missing ranges.

Pseudocode:

def summaryRanges(nums, lower, upper):
    result = []
    prev = lower-1  # initializing prev to lower-1 to handle the case where the first element of the array is lower.
    for i in range(len(nums)):
        if nums[i] - prev >= 2:
            result.append(getRange(prev+1, nums[i]-1))
        prev = nums[i]
    
    # Check if there is any remaining range after the last element of the array.
    if upper - prev >= 1:
        result.append(getRange(prev+1, upper))
    return result

def getRange(start, end):
    # returns the range in the format "start->end"
    if start == end:
        return str(start)
    else:
        return str(start) + "->" + str(end)

Time complexity: O(n), where n is the length of the input array nums. Space complexity: O(1), as we are only using constant amount of extra space to store the result list and a few variables.

1