# Very simple C++ solution

• Firstly, we put each element x in nums[x - 1]. Since x ranges from 1 to N, then x - 1 ranges from 0 to N - 1, it won't exceed the bound of the array.
Secondly, we check through the array. If a number x doesn't present in nums[x - 1], then x is absent.

``````class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
int i = 0;
while (i < nums.size()) {
if (nums[i] != nums[nums[i]-1]) swap(nums[i], nums[nums[i]-1]);
else i++;
}
for (i = 0; i < nums.size(); i++) {
if (nums[i] != i + 1) res.push_back(nums[i]);
}
return res;
}
};
``````

• @ivancjw Nice one, how did you come up with the logic of swapping? Is it some kind of a trick for problems where elements have to maintain ordering with their index numbers ?

• @sujiths52 Since the elements range from 1 to N, then each element is corresponding to a index. Maybe you can be inspired by counting sort.

• @ivancjw
are u sure it is right ?

try {3,2,5,4,3}

• @ivancjw
oh i forgot ,that int i is not been increased

• @ivancjw can you tell me what
nums[nums[i]-1]
does??

• @isalirezag because numbers range from 1 to n while the array is indexed from 0 to n-1.

• @sujiths52 @sujiths52 yeah I got that, my question is:
I know that nums[i] is gonna tell us the the ith value in nums, but what nums[nums[i]-1] is gonna tell us?
I apologize if this is kinda a bad question, im just a super beginner.

• This is a perfect idea!

• @isalirezag Hi, I have add a brief explanation to the post. Hope it helps :)

• Is that a O(n) solution?

• Is that a O(n) solution?

Really interesting, seems like in worst case it'll be O(n^2) solution, but it's runtime beats 76% solutions

• @zhiganoff worst case is not N^2 because the swaps put the numbers in place. If the first index needs to swap with everyone else, then everyone else has been corrected and the loop finishes without further swaps.

• This post is deleted!

• @zhiganoff It is O(n), because every swap put a new number in correct location. There is totally n number.

• you may forget this statement:

Could you do it without extra space and in O(n) runtime?

• without extra space???

• @gaussic no extra space is used in ivancjw 's solution. all the operations are done within the original array

• @isalirezag Our purpose is to change the order of the original array, and make that every element is placed in right position ( to make sure : index = value - 1). nums[i]-1 is the right place for the element in position i ( nums[i] ), which means nums[nums[i]-1] should equal to nums[i]; if don't, then swap them.

• I‘m a super beginner,my question is that the O(n) mean we must finish the calculation within n times？

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