InterviewCrunch

Login

Set Mismatch

Question

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.

Note that the array is unsorted.

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

Output: [2,3]

2 appears twice and 3 is missing.

Input: nums = [1,1]

Output: [1,2]

1 appears twice and 2 is missing.

Constraints:

  • 2 ≤ nums.length ≤ 104
  • 1 ≤ nums[i] ≤ 104

Clarify the problem

What are some questions you'd ask an interviewer?

Understand the problem

Which approach is most efficient for finding a duplicate and missing number in an unsorted array?
Sort the array first, then scan for duplicate and missing numbers
Use a hash set to track seen numbers, then find the duplicate and missing numbers
Use binary search to find the duplicate and missing numbers
Compare each number with every other number to find the duplicate

Take a moment to understand the problem and think of your approach before you start coding.