Problem statement

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

Solution

All we need to do is to traverse number by number and when we see that number is not equal to previous, we create interval. Also we add lower - 1 to the beginning and upper + 1 to the end and we need to deal with cases when interval has only one element inside.

Complexity

Time complexity is $\mathcal{O}(n)$ to traverse all intervals, space complexity is $\mathcal{O}(1)$

Code

class Solution:
    def findMissingRanges(self, nums, lower, upper):
        nums = [lower - 1] + nums + [upper + 1]
        n, missing = len(nums), []
        
        for i in range(1, n):
            if nums[i] != nums[i-1] + 1:
                a, b = nums[i-1] + 1, nums[i] - 1
                if a == b: missing.append(str(a))
                else: missing.append(str(a) + "->" + str(b))
                
        return missing