Watch 10 video solutions for Set Mismatch, a easy level problem involving Array, Hash Table, Bit Manipulation. This walkthrough by NeetCodeIO has 15,608 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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]
Constraints:
2 <= nums.length <= 1041 <= nums[i] <= 104Problem Overview: You are given an array containing numbers from 1 to n. One number appears twice and another number is missing. The task is to identify the duplicated value and the missing value efficiently.
Approach 1: Sum and Difference Method (O(n) time, O(1) space)
This approach uses simple math instead of extra data structures. For a perfect sequence from 1..n, the expected sum is n(n+1)/2. When you iterate through the array and compute the actual sum, the difference between the expected and actual values reveals the relationship between the missing and duplicated numbers. You can also compute the sum of squares difference to isolate both values. The key insight is that the duplicate adds extra value while the missing number subtracts from the expected total. By solving the resulting equations, you recover both numbers in a single pass. This method runs in O(n) time and uses O(1) extra space, making it an efficient mathematical alternative when you want to avoid additional memory. It works well for problems involving arithmetic properties of an array.
Approach 2: Frequency Counting with HashMap (O(n) time, O(n) space)
This method relies on counting how many times each number appears. Iterate through the array and store frequencies in a HashMap. When a value appears twice, you immediately identify the duplicate. After building the frequency map, iterate from 1 to n and check which number does not appear in the map—that number is the missing value. The key idea is constant-time lookup using a hash table, which makes detection straightforward. The algorithm runs in O(n) time because each element is processed once and hash lookups are O(1) on average. The tradeoff is O(n) additional space for storing counts. This approach is often the most intuitive if you are comfortable with frequency counting patterns.
Recommended for interviews: The HashMap approach is usually the first solution candidates present because it directly models the problem using frequency counting. It clearly demonstrates understanding of hash tables and runs in optimal O(n) time. Strong candidates then optimize further using the mathematical sum-and-difference technique, which reduces space to O(1). Showing both approaches signals strong problem-solving depth: the HashMap version proves correctness quickly, while the math-based solution demonstrates deeper algorithmic insight with array properties.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sum and Difference Method | O(n) | O(1) | When you want optimal space and can leverage arithmetic properties of numbers 1..n |
| Frequency Counting with HashMap | O(n) | O(n) | General case when clarity matters and extra memory is acceptable |