163. Missing Ranges (Array)

링크 - https://leetcode.com/problems/missing-ranges/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

처음과 끝 부분의 edge case를 잘 처리해야 하는 문제이다. 이는 lower-1을 맨 앞에, upper+1을 맨 뒤에 추가함으로써 해결이 가능하다.

Code

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]:
        ans = []
        new_nums = [lower-1] + nums + [upper+1]
        for i in range(len(new_nums) - 1):
            diff = new_nums[i+1] - new_nums[i]
            if diff > 1:
                ans.append([new_nums[i] + 1, new_nums[i+1] - 1])

        return ans
        
# Solution with O(1) space complexity
class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]:
        n = len(nums)
        ans = []

        if n == 0:
            ans.append([lower, upper])
            return ans

        if lower < nums[0]:
            ans.append([lower, nums[0] - 1])

        for i in range(n-1):
            if nums[i+1] - nums[i] <= 1:
                continue
            ans.append([nums[i] + 1, nums[i+1] - 1])

        if upper > nums[n-1]:
            ans.append([nums[n-1] + 1, upper])

        return ans

Complexity

Time Complexity: O(n)

Space Complexity: O(n)