NUHMAN.com

Introduction

LeetCode 163 requires us to find all the missing ranges in a sorted list of integers. The input is an inclusive range [lower, upper] and an array of integers nums, where nums is sorted in ascending order. We need to return the list of missing ranges between lower and upper that are not in nums.

Problem Statement

Given an integer array nums sorted in ascending order, and two integers lower and upper, return the list of all the missing ranges in the form of ["start->end"] (if the range is a single number, the format is "start").

Function Signature:

go

func findMissingRanges(nums []int, lower int, upper int) []string

• Input:
• nums: A list of integers where 0 <= len(nums) <= 10000.
• lower and upper: Integers where -10^9 <= lower <= upper <= 10^9.
• Output:
• A list of strings representing the missing ranges between lower and upper.

Approach

We can approach this problem by iterating over the nums array and checking for gaps between consecutive elements. If there's a gap between two elements, that means there's a missing range between them. The ranges can be formatted in the form start->end if the gap contains multiple missing numbers, or just start if it's a single missing number.

1. Edge Case: If nums is empty, the entire range from lower to upper is missing.
2. Iterate over the array:

• For each element in nums, check if there's a gap between the current element and the next element. If there's a gap, generate a missing range.

1. Post-processing: After the loop, check if there's a gap between the last element of nums and upper, and generate a missing range if necessary.
2. Return the list of missing ranges.

Time Complexity:

• O(n) where n is the length of the nums array, as we only iterate through the array once.

Space Complexity:

• O(k) where k is the number of missing ranges, as that's the space used to store the result.

Go Implementation

go

func findMissingRanges(nums []int, lower int, upper int) []string {
    result := []string{}
    
    // Add the range before the first number if there's a gap
    if len(nums) == 0 {
        if lower == upper {
            result = append(result, fmt.Sprintf("%d", lower))
        } else {
            result = append(result, fmt.Sprintf("%d->%d", lower, upper))
        }
        return result
    }
    
    // Check before the first number
    if nums[0] > lower {
        if nums[0] == lower + 1 {
            result = append(result, fmt.Sprintf("%d", lower))
        } else {
            result = append(result, fmt.Sprintf("%d->%d", lower, nums[0]-1))
        }
    }
    
    // Check between all the numbers in the array
    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] + 1 {
            if nums[i] == nums[i-1] + 2 {
                result = append(result, fmt.Sprintf("%d", nums[i-1] + 1))
            } else {
                result = append(result, fmt.Sprintf("%d->%d", nums[i-1] + 1, nums[i] - 1))
            }
        }
    }
    
    // Check after the last number
    if nums[len(nums)-1] < upper {
        if nums[len(nums)-1] == upper - 1 {
            result = append(result, fmt.Sprintf("%d", upper))
        } else {
            result = append(result, fmt.Sprintf("%d->%d", nums[len(nums)-1] + 1, upper))
        }
    }
    
    return result
}

Explanation of the Code:

1. Handle Edge Case (Empty Array):

• If nums is empty, we simply return the entire range from lower to upper.

2. Check Range Before the First Element:

• If the first number in nums is greater than lower, we check if the gap between lower and the first element in nums is a single missing number or a range.

3. Check for Missing Ranges Between Elements:

• We loop through the nums array and for each element, we check if there's a gap between the current element and the previous one. If there's a gap, we format the missing range accordingly.

4. Check Range After the Last Element:

• After processing the elements in nums, we check if there's a gap between the last element and upper. If there is, we generate a missing range.

Example

Example 1:

go

nums := []int{0, 1, 3, 50, 75}
lower := 0
upper := 99
result := findMissingRanges(nums, lower, upper)
fmt.Println(result) // Output: ["2", "4->49", "51->74", "76->99"]

Explanation:

• The missing ranges are:
• From 2 to 2
• From 4 to 49
• From 51 to 74
• From 76 to 99

Example 2:

go

nums := []int{}
lower := 1
upper := 1
result := findMissingRanges(nums, lower, upper)
fmt.Println(result) // Output: ["1"]

Explanation:

• Since nums is empty, the entire range from 1 to 1 is missing, so the output is ["1"].

Example 3:

go

nums := []int{1, 2, 3, 4}
lower := 0
upper := 5
result := findMissingRanges(nums, lower, upper)
fmt.Println(result) // Output: ["0", "5"]

Explanation:

• The missing numbers are 0 before the array and 5 after the array.

Conclusion

LeetCode 163 is a problem where we need to find the missing ranges between a given lower and upper in a sorted array. By efficiently checking the gaps between consecutive elements, we can identify the missing ranges and return them in the required format. The approach runs in linear time, making it efficient for large arrays.