Find All Duplicates in an Array

LeetCode 442: Find All Duplicates in an Array Solution & Explanation

Problem Overview

TL;DR: By utilizing the Cyclic Sort pattern, we can place each number into its correct index (mapping value $x$ to index $x-1$) in $O(n)$ time, allowing us to identify duplicates by checking which indices hold the wrong values.

The problem asks us to identify all integers that appear twice in a given integer array nums. The array has length n, and all integers within it fall within the range [1, n]. Importantly, every element appears either once or twice. The solution must be efficient, running in linear time, and must not use any extra space for data structures like hash sets (constant auxiliary space).

This is a classic interview question, often referred to as LeetCode 442, which tests a candidate's ability to recognize relationships between array values and array indices.

Brute Force Approach for Find All Duplicates in an Array

A naive approach to solving Find All Duplicates in an Array typically involves counting the frequency of each number.

The most straightforward method is to use a Hash Map (or Hash Set) to store the elements we have encountered so far. As we iterate through the array, we check if the current number already exists in our set.

1. Initialize an empty Hash Set.
2. Iterate through nums.
3. If nums[i] is in the set, add it to the output list (it is a duplicate).
4. Otherwise, add nums[i] to the set.

Pseudo-code:

function findDuplicates(nums):
    seen = new HashSet()
    duplicates = []
    for num in nums:
        if num in seen:
            duplicates.add(num)
        else:
            seen.add(num)
    return duplicates

Why this fails: While this solution runs in $O(n)$ time, it requires $O(n)$ space to store the seen set. The problem constraints explicitly demand constant auxiliary space ($O(1)$).

Another brute force method involves sorting the array first ($O(n \log n)$) and then checking adjacent elements. This fails the time complexity constraint of $O(n)$.

Algorithm Strategy: Array - Cyclic Sort

We will implement the Cyclic Sort pattern in two passes (or a single pass with specific logic, but the two-pass approach is cleaner for explanation).

1. Placement Phase (Cyclic Sort): Iterate through the array with a pointer i. For each element nums[i]:

   • Calculate its correct destination index: correct_index = nums[i] - 1.
   • If nums[i] is not already at correct_index AND the value at correct_index is not equal to nums[i]:
     • Swap nums[i] and nums[correct_index].
     • Decrement i (or stay at the same i) to re-evaluate the new number that was just swapped into the current position.
   • If the value at correct_index IS already nums[i], we simply move to the next index. This means we have found a duplicate, but we leave it in the "wrong" position for now.

2. Identification Phase: Iterate through the sorted array.

   • Check if nums[i] != i + 1.
   • If this condition is true, it means nums[i] is a duplicate (it is occupying the seat of the missing number i+1).
   • Add nums[i] to the result list.

This strategy strictly adheres to $O(n)$ time because each number is swapped to its correct position at most once. It uses $O(1)$ space because we modify the input array in-place.

Execution Flow

Let's trace the algorithm with nums = [4, 3, 2, 7, 8, 2, 3, 1].

Phase 1: Cyclic Sort

• i = 0, val = 4: Target index is 3. nums[3] is 7. Swap.
  • Array: [7, 3, 2, 4, 8, 2, 3, 1]
• i = 0, val = 7: Target index is 6. nums[6] is 3. Swap.
  • Array: [3, 3, 2, 4, 8, 2, 7, 1]
• i = 0, val = 3: Target index is 2. nums[2] is 2. Swap.
  • Array: [2, 3, 3, 4, 8, 2, 7, 1]
• i = 0, val = 2: Target index is 1. nums[1] is 3. Swap.
  • Array: [3, 2, 3, 4, 8, 2, 7, 1]
• i = 0, val = 3: Target index is 2. nums[2] is 3. Match found. Since nums[2] is already 3, we stop swapping for this position and move i forward.
• i = 1, val = 2: Correct position is index 1. It is already there. Move i.
• i = 2, val = 3: Correct position is index 2. It is there. Move i.
• i = 3, val = 4: Correct position is index 3. It is there. Move i.
• i = 4, val = 8: Target index is 7. nums[7] is 1. Swap.
  • Array: [3, 2, 3, 4, 1, 2, 7, 8]
• i = 4, val = 1: Target index is 0. nums[0] is 3. Swap.
  • Array: [1, 2, 3, 4, 3, 2, 7, 8]
• i = 4, val = 3: Target index is 2. nums[2] is 3. Match found. Move i.
• ...Proceed through rest of array. No more swaps occur.

Final sorted state: [1, 2, 3, 4, 3, 2, 7, 8]

Phase 2: Identification

• Index 0: nums[0] == 1. Correct.
• Index 1: nums[1] == 2. Correct.
• Index 2: nums[2] == 3. Correct.
• Index 3: nums[3] == 4. Correct.
• Index 4: nums[4] == 3. Expected 5. Duplicate found: 3.
• Index 5: nums[5] == 2. Expected 6. Duplicate found: 2.
• Index 6: nums[6] == 7. Correct.
• Index 7: nums[7] == 8. Correct.

Result: [3, 2]

Proof of Correctness

The algorithm relies on the fact that indices are unique. If the array contains the range [1, n], each number k has exactly one reserved index k-1.

1. If a number k appears once, the Cyclic Sort places it exactly at nums[k-1].
2. If a number k appears twice, the first instance takes the slot nums[k-1]. The second instance cannot occupy nums[k-1] because it is already taken by the first k.
3. Consequently, the second instance of k is forced to remain in a slot j where j != k-1.
4. Since the problem guarantees elements appear at most twice, checking nums[i] != i+1 is sufficient to identify these displaced duplicates.

Pattern Reuse Notes

The Cyclic Sort pattern is a powerful tool for optimal interview solutions involving arrays with continuous ranges.

• LeetCode 268: Missing Number: Uses Cyclic Sort to find the one number missing from the range 0 to n.
• LeetCode 448: Find All Numbers Disappeared in an Array: Almost identical to LeetCode 442, but instead of collecting the numbers that appear twice, you collect the indices that hold the wrong numbers (the missing ones).
• LeetCode 287: Find the Duplicate Number: Similar constraint, but finding a single duplicate. Often solved with Floyd's Cycle Detection, but Cyclic Sort also works if modifying the array is allowed.
• LeetCode 41: First Missing Positive: The hardest variation. You must ignore numbers outside the 1 to n range while Cyclic Sorting to find the first index that doesn't match.

Reference Implementation

C++ Solution for LeetCode 442

1class Solution {
2public:
3    vector<int> findDuplicates(vector<int>& nums) {
4        int n = nums.size();
5        int i = 0;
6        
7        // Phase 1: Cyclic Sort
8        while (i < n) {
9            int correctIndex = nums[i] - 1;
10            // Swap if the element is not at the correct index
11            // AND the correct index doesn't already contain the correct element
12            if (nums[i] != nums[correctIndex]) {
13                swap(nums[i], nums[correctIndex]);
14            } else {
15                i++;
16            }
17        }
18        
19        // Phase 2: Identify Duplicates
20        vector<int> duplicates;
21        for (int j = 0; j < n; j++) {
22            // If the number at index j is not j+1, it's a duplicate
23            if (nums[j] != j + 1) {
24                duplicates.push_back(nums[j]);
25            }
26        }
27        
28        return duplicates;
29    }
30};

Java Solution for LeetCode 442

1class Solution {
2    public List<Integer> findDuplicates(int[] nums) {
3        int i = 0;
4        int n = nums.length;
5        
6        // Phase 1: Cyclic Sort
7        while (i < n) {
8            int correctIndex = nums[i] - 1;
9            // If the current number is not at its correct index
10            // and the target position doesn't already hold the correct number
11            if (nums[i] != nums[correctIndex]) {
12                swap(nums, i, correctIndex);
13            } else {
14                i++;
15            }
16        }
17        
18        // Phase 2: Identify Duplicates
19        List<Integer> duplicates = new ArrayList<>();
20        for (int j = 0; j < n; j++) {
21            if (nums[j] != j + 1) {
22                duplicates.add(nums[j]);
23            }
24        }
25        
26        return duplicates;
27    }
28    
29    private void swap(int[] arr, int first, int second) {
30        int temp = arr[first];
31        arr[first] = arr[second];
32        arr[second] = temp;
33    }
34}

Python Solution for LeetCode 442

1class Solution:
2    def findDuplicates(self, nums: List[int]) -> List[int]:
3        i = 0
4        n = len(nums)
5        
6        # Phase 1: Cyclic Sort
7        while i < n:
8            correct_index = nums[i] - 1
9            # Check if nums[i] is at the correct position
10            if nums[i] != nums[correct_index]:
11                # Swap nums[i] with the element at its correct position
12                nums[correct_index], nums[i] = nums[i], nums[correct_index]
13            else:
14                i += 1
15                
16        # Phase 2: Identify Duplicates
17        duplicates = []
18        for j in range(n):
19            if nums[j] != j + 1:
20                duplicates.append(nums[j])
21                
22        return duplicates