448. Find All Numbers Disappeared in an Array — LeetCode(Python)

I got you!

Problem:

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.

Solution(s):

1. Sets —

Solution —

setn = set(nums)
l = []
for i in range(1, len(nums)+1):
    if i not in setn:
        l += [i]
return l

Explanation —

We create a set of all numbers in the array nums. And then, we iterate over the number range (1, n). We then add the missing numbers in a list l and return the list.

Time and Space Complexity —

To create a set we would need linear time and linear space. Then, the for loop also takes linear time.

Thus, if n is the length of the array nums,

Time Complexity: O(n)

Space Complexity: O(n)

2. Cool Trick —

Solution —

for num in nums:
    pos = abs(num) - 1
    if nums[pos] > 0:
    nums[pos] *= -1
            
ans = []
for i in range(len(nums)):
    if nums[i] > 0:
        ans += [i+1]
                
return ans

Explanation —

We iterate over the array nums and change the values at INDEX(think) nums[i] to negative, i.e. multiply by -1. So, an example array would look like:

[4,3,2,7,8,2,3,1] , becomes

[-4,-3,-2,-7,8,2,-3,-1]

Now, we see that there are two numbers that still are positive.

We loop over the array again and return the positions of these two numbers as a list.

Time and Space Complexity —

Looping over the array takes linear time and according to the constraints of the problem, the returned list comes under constant time.

Thus, if n is the number of elements in the list nums,

Time Complexity: O(n)

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏