Find All Duplicates in an Array

Problem

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

Sorting Solution: O(nlgn) time, O(1) space

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        Arrays.sort(nums);
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) res.add(nums[i]);
        }
        return res;
    }
}

Marking by Negative Solution: O(n) time, O(1) space

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int num : nums) {
            int index = Math.abs(num) - 1;
            if (nums[index] > 0) nums[index] *= -1;
            else res.add(Math.abs(num)); 
        }
        //If we don't want to change the input, call Math.abs() on each num in the array before return
        return res;
    }
}

Analysis

The sorting solution simply sorts the given array and checks two adjacent values
If some number is equal to its previous number, we add it to our res

The second solution make use of given array property that 1 <= nums[i] <= n, where n = nums.length
Therefore, we can get the index of array from its value first
Then we mark the value at current index by nums[index] *= -1 if the value it's positive
If that value is not positive, we know that because we marked it before
Hence we meet duplicates, and we add the index not nums[index] to our res
To get a valid index, we fist do Math.abs(). To get index from 0 we do - 1