Find All Duplicates in an Array

Problem

Given an integer array nums where every value is in the range [1, n] (n = length) and each appears once or twice, return all the values that appear exactly twice. Return them in the order their second occurrence is encountered.

Constraints

• n == nums.length
• 1 ≤ n ≤ 10⁵
• 1 ≤ nums[i] ≤ n
• each value appears once or twice

Approach — Hashing & Counting

This is a Hashing & Counting problem. The idea: store what you've seen in a hash map for O(1) lookups, trading a little space to avoid a nested scan. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def findDuplicates(self, nums):
        res = []
        for x in nums:
            i = abs(x) - 1
            if nums[i] < 0:
                res.append(abs(x))
            else:
                nums[i] = -nums[i]
        return sorted(res)

Java

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        List<Integer> res = new ArrayList<>();
        for (int n : nums) {
            if (!seen.add(n)) res.add(n); // add() returns false if already present
        }
        return res;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.