LeetCode - Find All Numbers Disappeared in an Array Fastest Solution

Hello Code Recipian! Welcome back to another article on leetcode problem solutions. Today we will be solving leetcode problem no.448 Find All Numbers Disappeared in an Array.

Problem Statement: Find All Numbers Disappeared in an Array

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

Example 1:

Input: [2, 3, 1, 8, 2, 3, 5, 1]
Output: 4, 6, 7
Explanation: The given array has numbers in the range 1 to 8. 4, 6 and 7 are the numbers missing from the given range.

Example 2:

Input: [2, 4, 1, 2]
Output: 3

Example 3:

Input: [2, 3, 2, 1]
Output: 4

Constraints:

• n == nums.length

• 1 <= n <= 10^5

• 1 <= nums[i] <= n

Solution

This question is an extension of the Missing Number problem that we discussed in our previous article. We can use the same cyclic sort technique to solve this problem as well, with slight modification. If you have not yet gone through that article we suggest you to go through that one first because it will help you understand this one better.

Let's see how the algorithm works in detail.

Algorithm

Below is a step-by-step explanation for the working of the algorithm:

1. Cyclic sort:

   The goal of cyclic sort is to put all numbers in its correct position in the array. 1 is placed at 0th index, 2 is placed at 1st index, 3 is placed at 2nd index and so on.

   
   

   Iterate through the elements of the array from start to end. In each iteration we perform the following operations:

   1. Calculate the correct index where the current element should be placed. We can use the below formula to calculate correct index: correctIdx = current number - 1

   2. Next check if the current element is in it's correct position (nums[i] == nums[correctIdx]):

      1. If yes, we don't have have to do anything, just increment the current index and move to the next iteration.

      2. If no, move the current number to its correct position by swapping the current number with the number at the correct index.

   3. Repeat steps a and b until we reach the end of nums array.

2. Find all the missing numbers:

   Iterate through the array once again from start to end. In each iteration check if the current number is in its correct position:

   1. If yes, do nothing, continue to next iteration.

   2. If no, it means we have found a duplicate. Therefore add the number that was actually supposed to be here (current index + 1) to the result array (let's call it missingNums).

3. Return final result:

   Finally, return missingNums array as result.

Simulation

Below is a pictorial depiction for the working of the algorithm:

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Rust Solution

Complexity Analysis

Time Complexity

Cyclic sort (First loop):

Time complexity for placing the elements in its correct position using cyclic sort takes O(n) time complexity. We explained why it is O(n) in greater detail in the time complexity section in the Missing Number article.

Finding the missing numbers (Second loop):

For finding the missing numbers, we iterate through the given nums array from start to end. Hence time complexity is O(n).

Therefore the overall time complexity of this algorithm is O(n).

Space Complexity

Space complexity is O(1) since it is an in-place algorithm and does not use any extra space.

That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to create more such articles in the future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.