Set Mismatch
Find the duplicated and missing values in [1, n] via cyclic sort.
3 min read
cyclic-sort
Problem#
nums should be a permutation of [1, n] but exactly one value was duplicated and another is missing. Return [duplicate, missing].
Examples#
[1,2,2,4]→[2, 3]
Constraints#
2 <= n <= 10^4.
Approach#
Cyclic sort. After placement, the index i where nums[i] != i + 1 reveals both the duplicate (nums[i]) and the missing (i + 1).
Solution#
class Solution {public: vector<int> findErrorNums(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; ) { if (nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]); else ++i; } for (int i = 0; i < n; ++i) if (nums[i] != i + 1) return {nums[i], i + 1}; return {-1, -1}; }};func findErrorNums(nums []int) []int { n := len(nums) for i := 0; i < n; { if nums[i] != nums[nums[i]-1] { nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i] } else { i++ } } for i := 0; i < n; i++ { if nums[i] != i+1 { return []int{nums[i], i + 1} } } return []int{-1, -1}}from typing import List
class Solution: def findErrorNums(self, nums: List[int]) -> List[int]: n = len(nums) i = 0 while i < n: j = nums[i] - 1 if nums[i] != nums[j]: nums[i], nums[j] = nums[j], nums[i] else: i += 1 for i in range(n): if nums[i] != i + 1: return [nums[i], i + 1] return [-1, -1]function findErrorNums(nums) { const n = nums.length; let i = 0; while (i < n) { const j = nums[i] - 1; if (nums[i] !== nums[j]) { [nums[i], nums[j]] = [nums[j], nums[i]]; } else { i++; } } for (let k = 0; k < n; k++) { if (nums[k] !== k + 1) return [nums[k], k + 1]; } return [-1, -1];}class Solution { public int[] findErrorNums(int[] nums) { int n = nums.length; int i = 0; while (i < n) { int j = nums[i] - 1; if (nums[i] != nums[j]) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } else { i++; } } for (int k = 0; k < n; k++) { if (nums[k] != k + 1) return new int[]{nums[k], k + 1}; } return new int[]{-1, -1}; }}function findErrorNums(nums: number[]): number[] { const n = nums.length; let i = 0; while (i < n) { const j = nums[i] - 1; if (nums[i] !== nums[j]) { [nums[i], nums[j]] = [nums[j], nums[i]]; } else { i++; } } for (let k = 0; k < n; k++) { if (nums[k] !== k + 1) return [nums[k], k + 1]; } return [-1, -1];}Editorial#
The mismatched slot after cyclic sort tells us both anomalies in one comparison. Compare against nums[nums[i] - 1] (home position’s current value) to skip when home is already correct.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#