Day-12 Find all the numbers disappeared in the array

This problem statement is a part of LeetCode's learning card Introduction to Data Structures Fun with Arrays-101.

Problem Statement

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

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

Example 1

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

Solution Approach

1. The range of elements and the value of elements is the same.
2. List can have duplicates as well. So, converting a list to set would mean removing duplicates and having only unique elements.
3. Subtracting the set containing numbers between range [1, n] and the set formed by removing duplicates. Would return the missing elements.
4. Convert the set to list.

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        return list(set([x for x in range(1, len(nums)+1)]) - set(nums))

Learnings

1. Time complexity - 0(n)
2. We are still using extra space by initializing a completely new list with elements between [1,n].
3. Need to figure out a way to optimize space.