Missing Ranges

The problem is asking to find the missing ranges in a sorted array. The range is given as [lower, upper]. We need to find all the ranges in which there are no numbers present from the array.

We can solve this problem by checking the gaps between successive numbers in the array. If the gap is more than 1, we know there are missing numbers.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]:
        # Add lower-1 and upper+1 to the array, so we don't need to deal with edge cases.
        nums = [lower-1] + nums + [upper+1]

        # Initialize an empty list to store missing ranges.
        missing_ranges = []

        # Loop through the array. As we added two extra elements, we run it to len(nums) - 1.
        for i in range(len(nums) - 1):
            # Calculate the difference between current number and next number.
            diff = nums[i+1] - nums[i]

            # If the difference is 2, then there is exactly one missing number.
            if diff == 2:
                missing_ranges.append([nums[i] + 1, nums[i] + 1])

            # If the difference is more than 2, then there is a missing range.
            elif diff > 2:
                missing_ranges.append([nums[i] + 1, nums[i+1] - 1])

        return missing_ranges

We first add lower-1 and upper+1 to the list. This way, we can treat the start and end of the range in the same way as we treat the rest of the numbers in the list, and avoid special casing them.

We then iterate over the list. For each pair of consecutive numbers, we check if there are numbers missing between them by subtracting the first number from the second. If the difference is 2, then there’s exactly one missing number, which we add to the list of missing ranges as a range of itself. If the difference is more than 2, then there’s a range of missing numbers, and we add the range to the list of missing ranges.

Finally, we return the list of missing ranges.