• 55.9%

https://leetcode.com/problems/find-all-duplicates-in-an-array/

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

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

https://discuss.leetcode.com/topic/64759/very-simple-c-solution

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.

https://discuss.leetcode.com/topic/64835/c-easy-o-n-time-and-o-1-extra-space-solution-through-swapping

C++ Easy O(n) time and O(1) extra space solution through swapping.

Given that each element is between 1 and n. All the elements occur either once or twice.

So, in first pass, we can swap all the elements to their respective positions.

In second pass, all the one-time occuring elements are supposed to be at their positions. The elements that violate this conditions are the elements of our interest (because they are at some other positions, in addition of being at their respective index, where they are not supposed to be).

C++ using another idea instead of swapping

idea: take advantage of sign bit in integer

#### python

https://discuss.leetcode.com/topic/64979/python-o-n-time-o-1-space

Python O(n) time O(1) space

O(1) space not including the input and output variables

The idea is we do a linear pass using the input array itself as a hash to store which numbers have been seen before. We do this by making elements at certain indexes negative. See the full explanation here

http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

#### java

https://discuss.leetcode.com/topic/64735/java-simple-solution

Java Simple Solution

https://discuss.leetcode.com/topic/64908/java-solution-without-destroying-the-input-array-o-n-time-o-1-space

Java solution without destroying the input array. O(n) time. O(1) space.

https://discuss.leetcode.com/topic/64805/java-easy-to-understand-solution-without-extra-space-and-in-o-n-time

Java Easy to understand solution without extra space and in O(n) time

The concept here is to negate each number’s index as the input is 1 <= a[i] <= n (n = size of array). Once a value is negated, if it requires to be negated again then it is a duplicate.