https://leetcode.com/problems/missing-ranges/

Tag: Array/List, recursion

Key Points：

1. A good problem to solve by the intuitive linear scan method and recursion
2. Have a taste of different ways to think of a problem

Solution: Linear Scan

 def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]:
    if not nums:
	      return [[lower, upper]] # lower <= upper constraint has been given
    res = []
    for num in nums:
		    # Two cases when we iterate on one num, it's either less or equal to lower
        if num == lower:
            lower += 1
        else:
		        # When lower is less than num, we find a missing range
		        # Pay attention to its the upper boundary and new lower value
            res.append([lower, num - 1])
            lower = num + 1
    # Tailing case where upper is larger than any nums.
    if lower <= upper:
        res.append([lower, upper])
    return res

Solution: Recursion

1. The problem is scaled down by reducing the size of the nums array.
2. Only check the first number in the array, compare with lower and decide if there is a missing range.
3. The base case where nums is empty may have two scenarios:
   1. lower ≤ upper
   2. lower > upper: This is different from the first method above. It may happen when we have iterated the last number and upper is larger

def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]:
    if not nums:
		    if lower <= upper:
		        return [[lower, upper]]
		    else:
				    return []
    res = []
    # Find a missing range
    if lower < nums[0]:
        res.append([lower, nums[0] - 1])
    # Repeat with the subsequence and a new lower bound
    lower = nums[0] + 1
    res.extend(self.findMissingRanges(nums[1:], lower, upper))
    return res

When thinking of the recursion, always focus on the base case and logic for current recursive call and assuming it has been able to handle the next recursive call. Don’t be trapped by over-thinking into multi-level recursive calls. For this question,

First step, we think of the base case where nums is empty.

Second step, assuming findMissingRanges can return results for nums[1:], we need to deal with nums[0] in current call, where we may or may not find a missing range. Assuming we have got the results for nums[1:] by the next call of findMissingRanges, we combine it with the missing range for current call. This will be the final return for current call.