LeetCode - Missing Number Fastest Solution

Hello Code Recipian! Welcome back to another article on leetcode problem solutions. Today we will be solving leetcode problem no. 268 Missing Number. This question is similar to Find All Numbers Disappeared in an Array problem that we discussed in another article.

Problem Statement: Missing Number

Given an integer array nums, containing n distinct numbers in the range 0 to n, return the only number in the range that is missing (Return the missing number, not index).

Example 1:

Input: [4, 0, 3, 1]
Output: 2
Explanation: Range is 0 to 4. 0, 1, 3, 4 are present in array. 2 is the missing number. 

Example 2:

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

Constraints:

• n == nums.length

• 1 <= n <= 10^4

• 0 <= nums[i] <= n

• All the numbers of nums are unique.

Solution

There are multiple approaches to solve this problem. In this article we will be discussing one of the most efficient ways to solve this problem, by using cyclic sort technique.

Cyclic sort technique is one of the fastest ways to solve problems involving missing numbers in a given range. As you can see, it is also evident from the from the leetcode submission results:

The idea behind cyclic sort is simple, for an unsorted array containing n numbers in the range 1 to n, cyclic sort iterates through the given array, and in each iteration we place one of the numbers in its correct position in the array. We do this repeatedly until the array is sorted.

Let's see how this works in detail.

Algorithm

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

1. Cyclic sort:

   Iterate through the elements of the given nums array from start to end. In each iteration perform the following steps:

   1. Calculate the correct index where the current number should be placed. Since there are n elements and the range is 0 to n, nth number should be placed at (n-1)th position in the array, i.e. 1 should be placed at 0th index, 2 should be placed at 1st index, 3 should be placed at 2nd index and so on. Therefore the formula to calculate correct index is:

      correctIdx = current number - 1 or correctIdx = nums[i] - 1

   2. Once the is correctIdx calculated, check if the current number is in its correct position in the array.

      1. If the current number is not in it's correct position, we move it to the correct position by swapping the number at the current index with the number at the correctIdx.

      2. If the current number is in it's correct position, we increment current index and move to the next iteration.

   3. Repeat steps a and b until all the elements in the nums array are placed at the correct position.

2. Find the missing number:

   After step 1, cyclic sort places all the elements in its correct position, except the missing number. So, we iterate through the array once more from start to end and in each iteration we check if the current index has the correct number. If the current index does not have the correct number, that means we have found the missing element. Therefore, we return the missing number, i + 1 as result.

Note: In the formula for calculating the correct index, correctIdx = nums[i] - 1, since the range is 0 to n, we need to handle an edge case where nums[i] = 0. For such cases, correctIdx = -1, if we encounter this, we need to continue iterating without performing any operation. We need not handle this edge case if the range was from 1 to n.

Simulation

Below is a pictorial depiction of 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):

Since we are not incrementing current index i for every iteration, it might seem that the time complexity is not linear. However if you observe carefully, in each iteration we either swap and place an element in its correct position or increment i if the number is already in its correct position. So, overall our algorithm makes a maximum of O(n) + O(n-1) iterations, which although is more than n iterations, it is asymptotically equivalent to O(n).

Finding the missing number (Second loop):

Finding the missing number takes O(n) time as we having to iterate through the given nums array and in the worst case when last number is missing we will end up iterating entire the nums array.

Therefore, the overall time complexity is O(n).

Space Complexity

Space complexity of this algorithm is O(1) since it is an in-place algorithm and we are not using 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.