442. Find All Duplicates in an Array

Problem Description

Given an integer array nums of length n where all integers in nums appear 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 3:

Input: nums = [1]
Output: []

Constraints:

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

Python Solution

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        result = []
        
        # Use the array indices as a hash table
        for num in nums:
            # Get the absolute value since we might have negated it
            index = abs(num) - 1
            
            # If the number at index is negative, we've seen this number before
            if nums[index] < 0:
                result.append(abs(num))
            # Otherwise, negate the number at index to mark it as seen
            else:
                nums[index] = -nums[index]
        
        # Restore the array (optional)
        for i in range(len(nums)):
            nums[i] = abs(nums[i])
            
        return result

Java Solution

class Solution {
    public List findDuplicates(int[] nums) {
        List result = new ArrayList<>();
        
        // Use the array indices as a hash table
        for (int num : nums) {
            // Get the absolute value since we might have negated it
            int index = Math.abs(num) - 1;
            
            // If the number at index is negative, we've seen this number before
            if (nums[index] < 0) {
                result.add(Math.abs(num));
            }
            // Otherwise, negate the number at index to mark it as seen
            else {
                nums[index] = -nums[index];
            }
        }
        
        // Restore the array (optional)
        for (int i = 0; i < nums.length; i++) {
            nums[i] = Math.abs(nums[i]);
        }
        
        return result;
    }
}

C++ Solution

class Solution {
public:
    vector findDuplicates(vector& nums) {
        vector result;
        
        // Use the array indices as a hash table
        for (int num : nums) {
            // Get the absolute value since we might have negated it
            int index = abs(num) - 1;
            
            // If the number at index is negative, we've seen this number before
            if (nums[index] < 0) {
                result.push_back(abs(num));
            }
            // Otherwise, negate the number at index to mark it as seen
            else {
                nums[index] = -nums[index];
            }
        }
        
        // Restore the array (optional)
        for (int& num : nums) {
            num = abs(num);
        }
        
        return result;
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function(nums) {
    const result = [];
    
    // Use the array indices as a hash table
    for (let num of nums) {
        // Get the absolute value since we might have negated it
        const index = Math.abs(num) - 1;
        
        // If the number at index is negative, we've seen this number before
        if (nums[index] < 0) {
            result.push(Math.abs(num));
        }
        // Otherwise, negate the number at index to mark it as seen
        else {
            nums[index] = -nums[index];
        }
    }
    
    // Restore the array (optional)
    for (let i = 0; i < nums.length; i++) {
        nums[i] = Math.abs(nums[i]);
    }
    
    return result;
};

C# Solution

public class Solution {
    public IList FindDuplicates(int[] nums) {
        IList result = new List();
        
        // Use the array indices as a hash table
        foreach (int num in nums) {
            // Get the absolute value since we might have negated it
            int index = Math.Abs(num) - 1;
            
            // If the number at index is negative, we've seen this number before
            if (nums[index] < 0) {
                result.Add(Math.Abs(num));
            }
            // Otherwise, negate the number at index to mark it as seen
            else {
                nums[index] = -nums[index];
            }
        }
        
        // Restore the array (optional)
        for (int i = 0; i < nums.Length; i++) {
            nums[i] = Math.Abs(nums[i]);
        }
        
        return result;
    }
}