How to Find Missing and Duplicate Elements

Today, let's discuss a problem that seems simple but is quite clever: finding the missing and duplicate elements. I've written about a similar problem in a previous article Common Bit Manipulations, but the techniques used in this problem are different from the last one.

This is LeetCode problem #645 "Set Mismatch." Here's a description of the problem:

Given an array nums of length N, which originally contains the elements [1..N] in no particular order, some errors have occurred. One element in nums is duplicated, which simultaneously causes another element to be missing. Your task is to 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?