442. Find All Duplicates in an Array

Description

Here

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?

Example: Input: [4,3,2,7,8,2,3,1]

Output: [2,3]

Solution

The intuition is from the following:

1. 1 ≤ a[i] ≤ n, which means the operation on the index is viable.
2. The duplication only happens twice, which gives us the intuition of using XOR or flip the value to negative

Code

Updated Code

public List<Integer> findDuplicates(int[] nums) {
    final List<Integer> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
    int indexToFlip = Math.abs(nums[i]) - 1;
    if (nums[indexToFlip] < 0) {
        final int val = indexToFlip + 1;
        result.add(val);
    }
    nums[indexToFlip] = -nums[indexToFlip];
    }
    return result;
}