442. Find All Duplicates in an Array

MediumArrayHash Table

Problem Description

This problem asks us to find all the numbers that appear twice in an array nums, where the array has a length n, and all elements in the array are within the range [1, n]. The elements in the array can either appear once or twice. The challenge is to come up with an algorithm that finds the numbers appearing twice without using more than constant extra space, and it should have a linear run time, i.e., O(n).

Intuition

The solution utilizes the properties of the array elements being within the range from 1 to n. The algorithm works by placing each number in its correct position, i.e., the number 1 should be in index 0, 2 should be in index 1, and so forth. This is done by swapping the elements until each index i contains the number i+1.

The intuition here is that if all numbers appear only once, then after this process, each index i should hold the value i+1. If a number appears twice, then there will be at least one discrepancy where the value at nums[i] wouldn't match i+1.

Iterate through each element in the array.
For each element, check if it is not in its correct position, i.e., nums[i] is not equal to nums[nums[i] - 1]. If it's not, swap the elements in the current index i and the index that the current number should be at, which is nums[i] - 1.
Repeat this step until every number in the array is either at its correct index or there's a duplicate that prevents it from being placed correctly.
Once the array is sorted in this manner, we can easily find duplicates because the number will not match its index +1. The list comprehension [v for i, v in enumerate(nums) if v != i + 1] does exactly that, creating a list of values that do not match i+1, which are the duplicates we're looking for.

By using array indices to store the state of whether a number has been seen or not, we achieve the goal using constant space (O(1)), while the swapping ensures we can detect duplicates efficiently.

Solution Approach

The algorithm operates based on the notion that if we could place each number at its correct index in the array, we can then just iterate through the array to find numbers that are not at their correct indices.

The steps involved in solving this problem are:

Loop over each index i in the array nums.
Inside the loop, we initiate another loop that swaps the current element nums[i] with the element at the index it should be at, which is nums[nums[i] - 1]. This continues as long as nums[i] is not already at the correct position.
To swap, we perform a tuple assignment nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1], which swaps the elements in-place without the need for extra storage.
After completing the outer loop, we know that for each index i, if nums[i] does not equal i + 1, it must be a duplicate because there can only be one such case per number, considering that elements are strictly in the range [1, n].
We construct the result array by iterating over nums with the condition if v != i + 1, using a list comprehension that iterates over nums and its indices (using enumerate), and creates a list of the values v that do not match their supposed index i+1.

This approach utilizes in-place swapping to achieve the sorting, which ensures that we are not using any additional space; thus, it adheres to the constant space complexity restriction. The solution guarantees that we do not re-visit any number more than twice, maintaining the O(n) time complexity. Once an element is in its correct position, it's not touched again, and discovering the duplicate takes a single pass through the sorted array.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Consider the array nums = [4, 3, 2, 7, 8, 2, 3, 1].

According to the algorithm:

We start with the first element: 4. Since 4 should be at index 3 (nums[3]), we swap it with the element at index 3, which is 7. The array now looks like [7, 3, 2, 4, 8, 2, 3, 1].
We still are at index 0, and now we have 7 there, which should be at index 6. After swapping 7 with 3 (at index 6), the array is [3, 3, 2, 4, 8, 2, 7, 1].
At index 0, there's 3 that should be at index 2. But index 2 also has 2, which is the correct element for that position. Hence, we proceed to the next index.
At index 1, we also have 3, which is out of place, reflecting a duplicate has been found. However, 3's correct spot (index 2) already has a 2 positioned correctly, so we move on.
Proceed with the other elements until each index i contains the number i+1 or it's determined that a duplication prevents it from being in the correct position.

After the outer loop is completed, the array is [1, 2, 3, 4, 3, 2, 7, 8]. Following step 5, we will iterate through the array and identify the numbers that are not in their correct positions. Here, 3 at index 4 should have been 5, and 2 at index 5 should have been 6. Hence, these are our duplicates.

So, the output according to the algorithm is [3, 2], which accurately reflects the numbers that appear twice in the array.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findDuplicates(self, numbers: List[int]) -> List[int]:
5        n = len(numbers)
6        # Iterate over the numbers
7        for i in range(n):
8            # Place each number at its correct position (number-1)
9            # since the numbers are from 1 to n
10            while numbers[i] != numbers[numbers[i] - 1]:
11                # Swap the elements to their correct positions
12                correct_idx = numbers[i] - 1
13                numbers[i], numbers[correct_idx] = numbers[correct_idx], numbers[i]
14      
15        # Now, find all the numbers that are not at their correct position
16        # which will be our duplicates since those have been
17        # placed correctly during the previous loop
18        return [number for i, number in enumerate(numbers) if number != i + 1]
19

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5  
6    // Main method to find all the duplicates in the array.
7    public List<Integer> findDuplicates(int[] nums) {
8        int n = nums.length;
9      
10        // Place each number in its correct position such that the number i is at index i-1.
11        for (int i = 0; i < n; ++i) {
12            // While the current number is not at its correct position, swap it.
13            while (nums[i] != nums[nums[i] - 1]) {
14                swap(nums, i, nums[i] - 1);
15            }
16        }
17      
18        // Initialize the list to hold the duplicates.
19        List<Integer> duplicates = new ArrayList<>();
20      
21        // Scan the array for duplicates; a duplicate is found if the number is not at its correct position.
22        for (int i = 0; i < n; ++i) {
23            if (nums[i] != i + 1) {
24                duplicates.add(nums[i]);
25            }
26        }
27      
28        // Return the list of duplicates.
29        return duplicates;
30    }
31  
32    // Helper method to swap two elements in the array.
33    private void swap(int[] nums, int i, int j) {
34        int temp = nums[i];
35        nums[i] = nums[j];
36        nums[j] = temp;
37    }
38}
39

1#include <vector>
2#include <algorithm> // For std::swap
3
4class Solution {
5public:
6    // Function to find all duplicates in an array.
7    // Each element appears either once or twice, and elements are in the range [1, n].
8    std::vector<int> findDuplicates(std::vector<int>& nums) {
9        int size = nums.size();
10      
11        // Reorder the array such that the number `i` is placed at the index `i - 1`
12        for (int i = 0; i < size; ++i) {
13            // Swap elements until the current element is at its correct position.
14            while (nums[i] != nums[nums[i] - 1]) {
15                std::swap(nums[i], nums[nums[i] - 1]);
16            }
17        }
18      
19        std::vector<int> duplicates; // Vector to hold the duplicates found
20        for (int i = 0; i < size; ++i) {
21            // If current element is not at its correct position, it must be a duplicate
22            if (nums[i] != i + 1) {
23                duplicates.push_back(nums[i]); // Record the duplicate
24            }
25        }
26
27        // Return the vector containing all the duplicates
28        return duplicates;
29    }
30};
31

1function findDuplicates(nums: number[]): number[] {
2  const size = nums.length;
3
4  // Reorder the array such that the number `i` will be placed at the index `i - 1`
5  for (let i = 0; i < size; ++i) {
6    // Keep swapping elements until the current element is at its correct position
7    while (nums[i] !== nums[nums[i] - 1]) {
8      // Swap nums[i] with the element at its target position
9      const temp = nums[i];
10      nums[i] = nums[nums[i] - 1];
11      nums[temp - 1] = temp;
12    }
13  }
14
15  const duplicates: number[] = []; // Array to hold the duplicates found
16  for (let i = 0; i < size; ++i) {
17    // If the element is not at its correct position, it is a duplicate
18    if (nums[i] !== i + 1) {
19      duplicates.push(nums[i]); // Record the duplicate
20    }
21  }
22
23  // Return the array containing all the duplicates
24  return duplicates;
25}
26

Time and Space Complexity

The given code follows the approach of cyclic sort where every element is placed in its correct position, i.e., the element 1 goes to index 0, element 2 goes to index 1, and so on.

Time Complexity

The time complexity of this function can be analyzed as follows:

We iterate through each of the n elements of the array once, giving us an initial time complexity of O(n).
Inside the while loop, we perform the operation of placing each element in its correct location.
Even though there is a nested loop (the while loop), the runtime still remains O(n). The reason is that each number is swapped at most once because once a number is in its correct index, it's no longer part of the while loop operation.
Therefore, every element is moved at most once, and the inner loop can run a maximum of n times for all elements in total, not for every individual element.

Given the above, the overall time complexity of the function is O(n).

Space Complexity

The space complexity is considered as follows:

Since we only use constant extra space (a few variables for the indices), the space complexity is O(1).
The output array does not count towards space complexity for the purpose of this analysis, as it is part of the function's output.

In conclusion, the time complexity is O(n) and the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know