442 - Find All Duplicates in an Array

Problem

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 appear twice.

You must write an algorithm that runs in O(n) time and uses only constant auxiliary space, excluding the space needed to store the output array.

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

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

Input: nums = [1]
Output: []

Constraints:

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

Approach

Send each value v to index v - 1. A value appearing twice can only claim its home slot once, so the second copy is pushed into some other value’s slot and since every value that appears does get home, the only slots it can land in belong to values that never appeared.

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        const int n = nums.size();
        int i = 0;
        while (i < n) {
            int correct = nums[i] - 1;
            if (nums[i] != nums[correct]) {
                swap(nums[i], nums[correct]);
            } else {
                i++;
            }
        }

        vector<int> res;
        for (int j = 0; j < n; j++)
            if (nums[j] != j + 1) res.push_back(nums[j]);
        return res;
    }
};

nums = [4, 3, 2, 7, 8, 2, 3, 1]
settles to  [1, 2, 3, 4, 3, 2, 7, 8]
                          ^  ^
index 4 should hold 5 but holds 3   ->  3 is a duplicate
index 5 should hold 6 but holds 2   ->  2 is a duplicate

• time: O(n) - each swap seats one value permanently, so at most n swaps in total, and i advances at most n times
• space: O(1) auxiliary — the output vector is excluded by the problem