Find All Duplicates In Array: Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, *return an array of all the integers that appears twice*.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:

Input: nums = [1,1,2]
Output: [1]

Example 2:

Input: nums = [1]
Output: []

Constraints:

• n == nums.length
• 1 <= n <= 10^5
• 1 <= nums[i] <= n
• Each element in nums appears once or twice.

Try this Problem on your own or check similar problems:

1. Number of Good Pairs
2. String Compression
3. Find Triangular Sum of an Array

Solution:

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

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Explanation:

Again we have harder restrictions on what we can use. In this case we cannot have a helper data structure since the requirement is to have constant space complexity. But notice that elements either appear once or twice so we can reuse the input array to somehow mark that element has already been seen before. The easiest way is to mark it’s correspoding index by negative value (note that this is only possible because the values in array are in range 1..n). To find the corresponding mapping index we take the abs of current value of element and subtract 1 (since arrays are 0-indexed). If the value at that index is already negative we already saw the same element before which means index + 1 is the number reappearing again so we place it in the result array. If the value at the index is positive it’s our first time seeing that number so we just make the value at corresponding index negative in case we encounter it again in the rest of the array. Let’s give an example:

nums = [1, 1, 2];

We iterate over the array, and first check the element at the index 0. In this case we have number 1, so we record it’s occurence at element-1 index, in this case nums[0], so the array now is nums = [-1, 1, 2]. Next at position 1 we have element 1 again, so we check the corresponding index and see it’s a negative value so 1 is reappearing and we place it in the result list. Next we have 2, but the number at element-1 index is positive which means we are seeing this number for the first time. We make the value at the correspoding index negative but we don’t add 2 to the result list. At the end input array will look like

nums = [-1, -1, 2].