How to Find Missing and Duplicate Elements
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 645. Set Mismatch | 🟢 |
Today, let's discuss a seemingly simple yet ingenious problem: finding the missing and duplicate elements. A similar problem was covered in a previous article Common Bit Manipulations, but the techniques used in this case are different.
This is LeetCode problem 645 "Set Mismatch", and I'll describe the problem:
Given an array nums of length N, originally containing the N elements from [1..N] in no particular order. However, some errors have occurred: one element in nums appears twice, leading to another element missing. 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 should return [2,3].
This problem can be easily solved by first traversing the array and using a hash table to record the frequency of each number, then traversing [1..N] to find which element appears twice and which is missing.
However, this conventional solution requires a hash table, resulting in O(N) space complexity. Given the problem's conditions, one might think of using a more elegant method to solve it.
Traversing the array in O(N) time complexity is unavoidable, but we can try to reduce the space complexity. Is it possible to find the duplicate and missing elements with an O(1) space complexity?