March LeetCoding Challenge 2021 — Day 2: Set Mismatch

Today we will solve the second problem from the March LeetCoding Challenge 2021 — Set Mismatch.

Problem Statement

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

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

Example 2:

Input: nums = [1,1]
Output: [1,2]

Solution

Approach 1 — Sorting: At first we can sort the array and find the missing and repeating number. To check the missing number we will find the difference between two adjacent numbers. If it is greater than 1, then the missing number will be the number in between those two numbers. For finding the repeating number, we will check whether two adjacent numbers are equal. If they are equal, then we have found our repeating number.

Store the values in the array and return them.

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

Space Complexity: O(1)

Approach 2 — HashMap: We can store the frequency of numbers in an HashMap . In another iteration, we will go through 1 to n , and check its occurrence, if a number’s occurrence is 2 then that number is repeating and if it is not present in the hashmap then that is the missing number.

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