LeetCode 448. Find All Numbers Disappeared in an Array

Description

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

Input: nums = [1,1]
Output: [2]

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Explanation

Find the length of nums list and check which number is missing in the list number range.

Python Solution

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        
        n = len(nums)
        
        nums = set(nums)
        
        results = []
        for i in range(1, n + 1):
            if i not in nums:
                results.append(i)
                
        return results
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.