Set Mismatch

Find the duplicated and missing values in [1, n] via cyclic sort.

Medium
Time O(n) Space O(1)
LeetCode
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#

Set Mismatch
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};
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.