March LeetCoding Challenge 2021 — Day 3: Missing Number

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

Problem Statement

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

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)

Tech-enthusiastic . Connect me — https://twitter.com/sourav__saikia

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store