March LeetCoding Challenge 2021 — Day 3: Missing Number

We are going to solve the 3rd problem from the March LeetCoding Challenge 2021.

Problem Statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Example 4:

Input: nums = [0]
Output: 1
Explanation: n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

Constraints:

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Solution

This problem can be solved in multiple approaches. We have to find a missing number from an array.

Approach 1 — Sorting: We can use sorting to solve this problem. Once the array is sorted, we can check the adjacent elements and check the difference between them. If the difference is greater than 1, then we have found our missing number, the number in between these two number at i-th and (i+1)-th index.

Time Complexity: O(nlogn), This time is required to sort the array

Space Complexity: O(1), No extra space is used

Approach 2 — HashSet: We can use HashSet to solve this problem. We will store the numbers in the HashSet and in the second iteration, we will check from 0 to n if any number is absent then we return it.

Time Complexity: O(n)

Space Complexity: O(n)

The code can be found here

sksaikia/LeetCode