Course4all
Join us on telegram
Home/dsa/Arrays & Hashing/Find All Duplicates in an Array

Find All Duplicates in an Array

Master this topic with zero to advance depth.

Find All Duplicates in an Array

Since all integers are in the range [1, n], we can use the array itself as a frequency map by negating values at indices corresponding to the numbers seen. If we encounter an already negative value, it's a duplicate.

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 solve the problem without using extra space and in O(n) runtime.

Visual Representation

nums = [4, 3, 2, 7, 8, 2, 3, 1] Index 0 (4): Mark index 3 -> [4, 3, 2, -7, 8, 2, 3, 1] Index 1 (3): Mark index 2 -> [4, 3, -2, -7, 8, 2, 3, 1] ... Index 5 (2): Index 1 is already negative (-3)! DUPLICATE FOUND: 2
Medium

Examples

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

2 and 3 appear twice in the array.

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

1 appears twice.

Approach 1

Level I: Brute Force (Nested Loops)

Intuition

We check every element against all subsequent elements to find duplicates. If a match is found, we add it to our result list (handling duplicates in the result list if necessary).

⏱ O(N²) where N is the length of the array.💾 O(1) (excluding the space for the result list).

Detailed Dry Run

ijnums[i]nums[j]Match?Result
0143No[]
2522Yes[2]
1633Yes[2, 3]
java
import java.util.*;

public class Main {
    public static List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    if (!res.contains(nums[i])) res.add(nums[i]);
                    break;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(findDuplicates(new int[]{4, 3, 2, 7, 8, 2, 3, 1}));
    }
}
Approach 2

Level II: HashSet / Frequency Array

Intuition

Use an auxiliary Hash Set or boolean array to track which numbers have been seen so far. If a number is already in the set, it's a duplicate.

⏱ O(N) traversal.💾 O(N) for the Hash Set.

Detailed Dry Run

NumSeen?ActionResult
4NoAdd to Set[]
3NoAdd to Set[]
2NoAdd to Set[]
2YESAdd to Result[2]
java
public List<Integer> findDuplicates(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    List<Integer> res = new ArrayList<>();
    for (int n : nums) {
        if (seen.contains(n)) res.add(n);
        else seen.add(n);
    }
    return res;
}
Approach 3

Level III: Optimal Solution (In-place Negation)

Intuition

Since all integers are in the range [1, n], we can use the array itself as a hash table. For each number x, we go to the index abs(x)-1. If the value at that index is already negative, we know we've seen x before, so x is a duplicate. Otherwise, we negate the value to 'mark' it as seen.

⏱ O(N) single pass through the array.💾 O(1) extra space (modifying the input array in-place).

Detailed Dry Run

Marking Process

nums = [4, 3, 2, 7, 8, 2, 3, 1]

[4, 3, 2, 7, 8, 2, 3, 1] Iter 1: x=4, Mark index 3 (4-1) ^ [4, 3, 2, -7, 8, 2, 3, 1] Iter 5: x=2, index 1 (2-1) is 3 (>0), mark ^ [4, -3, 2, -7, 8, 2, 3, 1] Iter 6: x=2, index 1 is -3 (<0). FOUND DUPLICATE!

| Num (x) | Index (|x|-1) | Value at Index | Action | Result | | :--- | :--- | :--- | :--- | :--- | | 4 | 3 | 7 | Mark: nums[3]=-7 | [] | | 3 | 2 | 2 | Mark: nums[2]=-2 | [] | | 2 | 1 | 3 | Mark: nums[1]=-3 | [] | | 7 | 6 | 3 | Mark: nums[6]=-3 | [] | | 2 | 1 | -3 | Already Negative! | [2] |

java
import java.util.*;

public class Main {
    public static List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] < 0) res.add(Math.abs(nums[i]));
            else nums[index] = -nums[index];
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(findDuplicates(new int[]{4, 3, 2, 7, 8, 2, 3, 1}));
    }
}
← Previous QuestionSubarray Sum Equals K
Next Question →Set Matrix Zeroes