Find All Numbers Disappeared in an Array

Use the array itself as a hash — negate the value at index `|nums[i]| - 1`; positives left are the missing.

Easy
Time O(n) Space O(1)
LeetCode
3 min read
array in-place-hash

Problem#

nums has n integers in [1, n] (with duplicates). Return all numbers in [1, n] missing from the array, in O(1) extra space.

Examples#

  • [4,3,2,7,8,2,3,1][5,6].
  • [1,1][2].

Constraints#

  • 1 <= n <= 10^5.

Approach#

For each v in nums, set nums[|v| - 1] to its negative (mark “seen”). After one pass, indices still holding positive values correspond to missing numbers.

Solution#

Find All Numbers Disappeared in an Array
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for (int v : nums) {
int i = abs(v) - 1;
if (nums[i] > 0) nums[i] = -nums[i];
}
vector<int> ans;
for (int i = 0; i < (int)nums.size(); ++i)
if (nums[i] > 0) ans.push_back(i + 1);
return ans;
}
};

Editorial#

Repurposing the sign bit as a “visited” marker keeps space O(1) while preserving the original value via abs. The technique generalizes to any “values in [1, n]” detect-missing/duplicate problem.

Complexity#

  • Time: O(n).
  • Space: O(1) extra.

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.