How to Find Missing and Duplicate Elements

Today we will discuss a seemingly simple yet very clever problem: finding the missing and duplicate elements. A similar problem was discussed in a previous article Common Bit Manipulations, but the techniques used this time differ from the last.

This is LeetCode Problem 645, "Set Mismatch" 错误的集合. Let me describe the problem:

Given an array nums of length N, which originally contained the N elements [1..N] in no particular order. However, some errors have occurred, with one element in nums appearing twice, leading to another element being missing. Please write an algorithm to find the values of the duplicate and missing elements in nums.

// Return two numbers, which are {dup, missing}
int[] findErrorNums(int[] nums);

// Return two numbers, which are {dup, missing}
vector<int> findErrorNums(vector<int>& nums);

# Return two numbers, which are {dup, missing}
def findErrorNums(nums: List[int]) -> List[int]:

// Return two numbers, which are {dup, missing}
func findErrorNums(nums []int) []int {}

// Return two numbers, which are {dup, missing}
var findErrorNums = function(nums) {}

For example, given the input: nums = [1,2,2,4], the algorithm returns [2,3].

This problem is actually quite easy to solve. First, traverse the array once and use a hash table to record the frequency of each number. Then, traverse the range [1..N] to identify which element is duplicated and which is missing. That's it.

However, the issue is that this conventional approach requires a hash table, which means an O(N) space complexity. Given the clever conditions provided in the problem—exactly one duplicate and one missing number in the range [1..N]—something unusual must be going on, right?

An O(N) time complexity to traverse the array is unavoidable, so let's think about how to reduce the space complexity. Is it possible to find the duplicate and missing elements with O(1) space complexity?