# c++ solution O(1) space

• The idea is very similar to problem 442. Find All Duplicates in an Array: https://leetcode.com/problems/find-all-duplicates-in-an-array/.

First iteration to negate values at position whose equal to values appear in array. Second iteration to collect all position whose value is positive, which are the missing values. Complexity is O(n) Time and O(1) space.

``````class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int len = nums.size();
for(int i=0; i<len; i++) {
int m = abs(nums[i])-1; // index start from 0
nums[m] = nums[m]>0 ? -nums[m] : nums[m];
}
vector<int> res;
for(int i = 0; i<len; i++) {
if(nums[i] > 0) res.push_back(i+1);
}
return res;
}
};
``````

• I have understood this idea, but would you like to share something about how to come up with this? I cannot find the regular in it. Thank you!

• @shizumi ah, i've finally got that.

• @shizumi I'm unable to understand, how does this solution work and how to come with such a solution ? Can you please explain ?

• @yashvardhan90 The basic idea here is to label all appeared numbers in the array. Since we don't want to introduce extra space and given all numbers are positive(from 1 to n), negate the value in the corresponding position is one choice. Ex, for input like [1, 2, 2], after the first sweep, it becomes [-1, -2, 2]. At position index=2, there is a positive value, which means it corresponding value 3 is not showing.
Hope this simple example gives you some lead :-)

• @RushRab Thank you!

• That's smart to use the sign to store the information whether the number appears or not :)

• can you explain how to solve the problems 442(find duplicated num) by this way? I have thought about it but i think it's different, Thanks !

• Awesome! Thank you

• @fuhao0728 The problem 442 asks to find all duplicate numbers. It can follow the same idea to negate the appeared number(index).

• @RushRab good idea!Thanks!

• @shizumi The trick is to take advantage of the fact that the numbers in the array lie in the range of array indices. Whenever that happens, you can apply this or a similar logic.
The condition 0<=a[i]<n is given for a reason. As I mentioned earlier, take advantage of that fact.

• wonderful solution i have never thought of!

• @fuhao0728 when you negate a value check if a value is already negative which means it is duplicate

• This post is deleted!

• This post is deleted!

• @BatCoder The negative element will be kept as same according to "nums[m] = nums[m]>0 ? -nums[m] : nums[m]".

• @RushRab Hi I just want to know why you add abs() here? It will be wrong if without abs(). Can you tell me what is the problem here? Thanks!

• @yexingxingzj Use abs() to get the right index due to we modify(negate) the original nums.

• OMG...That's horrible...

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.