# Java Simple Solution

• ``````public class Solution {
// when find a number i, flip the number at position i-1 to negative.
// if the number at position i-1 is already negative, i is the number that occurs twice.

public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
int index = Math.abs(nums[i])-1;
if (nums[index] < 0)
nums[index] = -nums[index];
}
return res;
}
}
``````

• Thank you for your solution. Very tricky!

• @PENETRATIVE

Thank you!

I was thinking we need a way to "hash" the same number together without using extra space. I am inspired by the range of the input value (1 - N), which seems fit the index of the input array (0 - N-1).

If I hash `num[i]` to index `num[i]-1`, then I need to store it at index `num[i]-1` smartly. I shouldn't make irrecoverable change to the element at that position, because I may need the element in the future. Again using the given range of input is (1 - N), if flip it to the opposite I can still recover it using `Math.abs`

• great solution, very clever. But I always hesitate when the solution involves modifying the input array. Generally is this an okay thing to do? Thoughts? Thanks.

• wow, what a tricky solution. GOOD JOB, BTW, do I know you?

• @jdrogin

Hello! I think it will be a good question to ask interviewer during the interview. In this solution, we can recover the original input array by doing `Math.abs` for all the elements before the function return.

• @YuxinCao excellent point. I'm convinced!

• Just wondering how this works.
For e.g. you are picking a value from array and you go to the point in array till this value to mark is negative.

For e.g., if you have array [2, 5, 88, 123, 3455]; then how come nums[index] will not give ArrayOutBound exception ???
int index = Math.abs(nums[i])-1;
if (nums[index] < 0)

• the numbers in the array, x, are between 0 and n (the length of the array)
0 <= x < n

so you will not have a number like 3000 in an array of length 4.

• @TechPrep Don't forget there is a assumption: "1 ≤ a[i] ≤ n (n = size of array)", there will not give ArrayOutBound exception

• @TechPrep please read the restrictions, ok? Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

• we can optimize the code a little bit. Because index can never be negative, we don't have to use `Math.abs(index + 1)`

``````if (nums[index] < 0)
``````

• @TechPrep : Problem statement : Given an array of integers, 1 ≤ a[i] ≤ n

• I was just wondering if we have something like {{4,3,2,2,2,2,3,1}}. In that case, this returns the answer to be [2,2,3]. But from my understanding, the output should be [3] only as it is the only element that appears twice. Or is it okay to assume this is correct because the question does not specify exactly twice.

• @aritra90tnp "some elements appear twice and others appear once"

• @sentimental Thanks for pointing that out. I missed that.

• good solution

• `````` res.add(Math.abs(index+1));
``````

Here you don't have to get absolute value since index + 1 will never be < 0

• if (nums[index] < 0)

since index is always positive, I do not think the code Math.abs(index + 1) is really necessary, I tried with res.add(index + 1), it passed.

But this is really tricky and great idea!

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