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 have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.
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
So in the problem, we have to find the missing and repeating number in the array. Here we will discuss 2 approaches to solve the problem.
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)
The code can be found here
