Find All Duplicates in Array

🎯

Find All Duplicates in Array

mediumCYCLIC_SORTAmazonFacebookGoogle

Imagine you have a list of employee IDs where some IDs appear twice due to a system glitch. You need to find all these duplicate IDs efficiently.

💡 This problem is about identifying duplicates in an array where numbers are in a specific range. Beginners often struggle because they try complex data structures or sorting without leveraging the problem's constraints, missing the elegant cyclic sort approach.

📋

Problem Statement

Given an integer array nums of length n where all the integers are in the range [1, n], some elements appear twice and others appear once. Find all the elements that appear twice in this array. Return the duplicates in any order.

1 ≤ n ≤ 10^51 ≤ nums[i] ≤ nEach integer appears once or twice

💡

Example

Input"[4,3,2,7,8,2,3,1]"

Output[2,3]

2 and 3 appear twice, all other numbers appear once.

• All elements are unique → output is []
• All elements are duplicates (each number appears twice) → output is all numbers
• Array of length 1 → output is []
• Duplicates appear at the start and end → output includes those duplicates

⚠️

Common Mistakes

Not checking if duplicate already added in brute force or sorting approach

Duplicates appear multiple times in output

✅ Add a condition to check if duplicate is already recorded before adding

Infinite loop in cyclic sort when swapping duplicates

Code gets stuck swapping same elements endlessly

✅ Only swap if nums[i] != nums[correct_index], else increment i

Using sorting without numeric comparator in JavaScript

Array sorts lexicographically, causing wrong order and wrong duplicates

✅ Use nums.sort((a,b) => a - b) for numeric sort

Not handling edge cases like single element or all unique

Code may crash or return incorrect duplicates

✅ Add checks or rely on algorithm correctness for these cases

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by checking every pair for duplicates, though it's inefficient. It builds intuition about what duplicates mean and why we need better methods.

Intuition

Check every element against every other element to find duplicates. If an element appears more than once, add it to the result.

Algorithm

1. Initialize an empty list to store duplicates.
2. For each element in the array, check all other elements for the same value.
3. If a duplicate is found and not already recorded, add it to the duplicates list.
4. Return the duplicates list.

💡 This approach is straightforward but involves nested loops, which can be hard to optimize without understanding the problem constraints.

</>

Code

def findDuplicates(nums):
    duplicates = []
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j] and nums[i] not in duplicates:
                duplicates.append(nums[i])
    return duplicates

# Driver code
if __name__ == '__main__':
    arr = [4,3,2,7,8,2,3,1]
    print(findDuplicates(arr))

Line Notes

duplicates = []Initialize list to store duplicates found so far

for i in range(n):Outer loop picks each element to compare

for j in range(i + 1, n):Inner loop compares current element with all subsequent elements

if nums[i] == nums[j] and nums[i] not in duplicates:Check if duplicate found and not already recorded

import java.util.*;
public class Solution {
    public static List<Integer> findDuplicates(int[] nums) {
        List<Integer> duplicates = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j] && !duplicates.contains(nums[i])) {
                    duplicates.add(nums[i]);
                }
            }
        }
        return duplicates;
    }

    public static void main(String[] args) {
        int[] arr = {4,3,2,7,8,2,3,1};
        System.out.println(findDuplicates(arr));
    }
}

Line Notes

List<Integer> duplicates = new ArrayList<>();Create list to store duplicates

for (int i = 0; i < n; i++) {Outer loop selects each element

for (int j = i + 1; j < n; j++) {Inner loop compares with subsequent elements

if (nums[i] == nums[j] && !duplicates.contains(nums[i])) {Check for duplicate and avoid repeats in result

#include <iostream>
#include <vector>
using namespace std;

vector<int> findDuplicates(vector<int>& nums) {
    vector<int> duplicates;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] == nums[j]) {
                bool alreadyFound = false;
                for (int d : duplicates) {
                    if (d == nums[i]) {
                        alreadyFound = true;
                        break;
                    }
                }
                if (!alreadyFound) duplicates.push_back(nums[i]);
            }
        }
    }
    return duplicates;
}

int main() {
    vector<int> arr = {4,3,2,7,8,2,3,1};
    vector<int> res = findDuplicates(arr);
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

vector<int> duplicates;Stores duplicates found

for (int i = 0; i < n; i++) {Outer loop picks element

for (int j = i + 1; j < n; j++) {Inner loop compares with others

if (nums[i] == nums[j]) {Check if duplicate found

function findDuplicates(nums) {
    const duplicates = [];
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] === nums[j] && !duplicates.includes(nums[i])) {
                duplicates.push(nums[i]);
            }
        }
    }
    return duplicates;
}

// Test
const arr = [4,3,2,7,8,2,3,1];
console.log(findDuplicates(arr));

Line Notes

const duplicates = []Initialize array to hold duplicates

for (let i = 0; i < n; i++) {Outer loop selects element

for (let j = i + 1; j < n; j++) {Inner loop compares with subsequent elements

if (nums[i] === nums[j] && !duplicates.includes(nums[i])) {Check for duplicate and avoid duplicates in output

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Two nested loops each up to n cause quadratic time. The duplicates list can grow up to n/2 in worst case.

💡 For n=20, this means about 400 comparisons, which is slow for large arrays.

Interview Verdict: Use only to introduce - too slow for large inputs

This approach is impractical for large inputs but helps understand the problem and motivates better solutions.

🧠

Sorting + Single Pass

💡 Sorting the array groups duplicates together, making it easier to find duplicates in a single pass. This approach is more efficient than brute force but still not optimal.

Intuition

Sort the array so duplicates are adjacent, then scan once to collect duplicates.

Algorithm

1. Sort the input array.
2. Initialize an empty list for duplicates.
3. Iterate through the array from start to end - 1.
4. If current element equals next element, add it to duplicates list if not already added.
5. Return the duplicates list.

💡 Sorting simplifies duplicate detection by placing equal elements next to each other, reducing complexity.

</>

Code

def findDuplicates(nums):
    nums.sort()
    duplicates = []
    n = len(nums)
    for i in range(n - 1):
        if nums[i] == nums[i + 1] and (len(duplicates) == 0 or duplicates[-1] != nums[i]):
            duplicates.append(nums[i])
    return duplicates

# Driver code
if __name__ == '__main__':
    arr = [4,3,2,7,8,2,3,1]
    print(findDuplicates(arr))

Line Notes

nums.sort()Sort array to bring duplicates together

duplicates = []Prepare list to store duplicates

for i in range(n - 1):Iterate through array except last element

if nums[i] == nums[i + 1] and (len(duplicates) == 0 or duplicates[-1] != nums[i]):Check adjacent elements and avoid duplicate entries

import java.util.*;
public class Solution {
    public static List<Integer> findDuplicates(int[] nums) {
        Arrays.sort(nums);
        List<Integer> duplicates = new ArrayList<>();
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1] && (duplicates.isEmpty() || duplicates.get(duplicates.size() - 1) != nums[i])) {
                duplicates.add(nums[i]);
            }
        }
        return duplicates;
    }

    public static void main(String[] args) {
        int[] arr = {4,3,2,7,8,2,3,1};
        System.out.println(findDuplicates(arr));
    }
}

Line Notes

Arrays.sort(nums);Sort input array to group duplicates

List<Integer> duplicates = new ArrayList<>();List to store duplicates

for (int i = 0; i < nums.length - 1; i++) {Traverse array except last element

if (nums[i] == nums[i + 1] && (duplicates.isEmpty() || duplicates.get(duplicates.size() - 1) != nums[i])) {Detect duplicates and avoid repeats

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> findDuplicates(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> duplicates;
    int n = nums.size();
    for (int i = 0; i < n - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            if (duplicates.empty() || duplicates.back() != nums[i]) {
                duplicates.push_back(nums[i]);
            }
        }
    }
    return duplicates;
}

int main() {
    vector<int> arr = {4,3,2,7,8,2,3,1};
    vector<int> res = findDuplicates(arr);
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array to cluster duplicates

vector<int> duplicates;Store duplicates found

for (int i = 0; i < n - 1; i++) {Loop through array except last element

if (nums[i] == nums[i + 1]) {Check if current and next elements are equal

if (duplicates.empty() || duplicates.back() != nums[i]) {Avoid adding duplicates multiple times

function findDuplicates(nums) {
    nums.sort((a, b) => a - b);
    const duplicates = [];
    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i] === nums[i + 1] && (duplicates.length === 0 || duplicates[duplicates.length - 1] !== nums[i])) {
            duplicates.push(nums[i]);
        }
    }
    return duplicates;
}

// Test
const arr = [4,3,2,7,8,2,3,1];
console.log(findDuplicates(arr));

Line Notes

nums.sort((a, b) => a - b);Sort array numerically to group duplicates

const duplicates = []Initialize duplicates array

for (let i = 0; i < nums.length - 1; i++) {Traverse array except last element

if (nums[i] === nums[i + 1] && (duplicates.length === 0 || duplicates[duplicates.length - 1] !== nums[i])) {Check adjacent duplicates and avoid repeats

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Sorting takes O(n log n), then a single pass O(n) to find duplicates. Space for duplicates list is O(n) in worst case.

💡 For n=20, sorting is about 20*log2(20) ≈ 86 operations, much faster than brute force.

Interview Verdict: Accepted but not optimal

This approach is acceptable but interviewers expect better solutions leveraging problem constraints.

🧠

Optimal Cyclic Sort In-Place

💡 This approach uses the problem's constraint that numbers are in [1, n] to place each number at its correct index. Duplicates are detected when a number is already at its correct position, enabling O(n) time and O(1) space.

Intuition

Place each number at the index equal to its value minus one. If a number is already at that index, it must be a duplicate.

Algorithm

1. Initialize an empty list to store duplicates.
2. Iterate over the array with index i.
3. While the current element is not at its correct index and not equal to the element at its target index, swap it to its correct position.
4. If a duplicate is detected (element equals the element at its correct index), move to next index.
5. After placement, iterate through the array to collect elements not at their correct index as duplicates.
6. Return the duplicates list.

💡 This algorithm rearranges elements in-place to detect duplicates without extra space, leveraging the input constraints.

</>

Code

def findDuplicates(nums):
    duplicates = []
    i = 0
    n = len(nums)
    while i < n:
        correct_index = nums[i] - 1
        if nums[i] != nums[correct_index]:
            nums[i], nums[correct_index] = nums[correct_index], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            duplicates.append(nums[i])
    return duplicates

# Driver code
if __name__ == '__main__':
    arr = [4,3,2,7,8,2,3,1]
    print(findDuplicates(arr))

Line Notes

duplicates = []Prepare list to collect duplicates

while i < n:Traverse array to place elements correctly

correct_index = nums[i] - 1Calculate target index for current element

if nums[i] != nums[correct_index]:If current element not at correct place, swap it

import java.util.*;
public class Solution {
    public static List<Integer> findDuplicates(int[] nums) {
        List<Integer> duplicates = new ArrayList<>();
        int i = 0;
        int n = nums.length;
        while (i < n) {
            int correctIndex = nums[i] - 1;
            if (nums[i] != nums[correctIndex]) {
                int temp = nums[i];
                nums[i] = nums[correctIndex];
                nums[correctIndex] = temp;
            } else {
                i++;
            }
        }
        for (i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                duplicates.add(nums[i]);
            }
        }
        return duplicates;
    }

    public static void main(String[] args) {
        int[] arr = {4,3,2,7,8,2,3,1};
        System.out.println(findDuplicates(arr));
    }
}

Line Notes

List<Integer> duplicates = new ArrayList<>();List to store duplicates found

while (i < n) {Traverse array to place elements at correct indices

int correctIndex = nums[i] - 1;Calculate correct index for current element

if (nums[i] != nums[correctIndex]) {Swap if element not at correct position

#include <iostream>
#include <vector>
using namespace std;

vector<int> findDuplicates(vector<int>& nums) {
    vector<int> duplicates;
    int i = 0;
    int n = nums.size();
    while (i < n) {
        int correctIndex = nums[i] - 1;
        if (nums[i] != nums[correctIndex]) {
            swap(nums[i], nums[correctIndex]);
        } else {
            i++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            duplicates.push_back(nums[i]);
        }
    }
    return duplicates;
}

int main() {
    vector<int> arr = {4,3,2,7,8,2,3,1};
    vector<int> res = findDuplicates(arr);
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

vector<int> duplicates;Stores duplicates found

while (i < n) {Loop to place elements at correct indices

int correctIndex = nums[i] - 1;Calculate target index for current element

if (nums[i] != nums[correctIndex]) {Swap elements to correct positions

function findDuplicates(nums) {
    const duplicates = [];
    let i = 0;
    const n = nums.length;
    while (i < n) {
        const correctIndex = nums[i] - 1;
        if (nums[i] !== nums[correctIndex]) {
            [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
        } else {
            i++;
        }
    }
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) duplicates.push(nums[i]);
    }
    return duplicates;
}

// Test
const arr = [4,3,2,7,8,2,3,1];
console.log(findDuplicates(arr));

Line Notes

const duplicates = []Initialize array to hold duplicates

while (i < n) {Loop to place elements at correct indices

const correctIndex = nums[i] - 1;Calculate correct index for current element

if (nums[i] !== nums[correctIndex]) {Swap elements if not in correct position

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is swapped at most once to its correct position, so linear time. No extra space except output list.

💡 For n=20, about 20 swaps or less, very efficient compared to previous methods.

Interview Verdict: Accepted and optimal

This is the best approach for this problem, demonstrating mastery of cyclic sort and in-place algorithms.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the optimal cyclic sort approach is best. Brute force is only for explanation; sorting is acceptable but not ideal.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	Yes	Mention only - never code
2. Sorting + Single Pass	O(n log n)	O(n)	No	Yes	Mention as improvement, code if stuck
3. Optimal Cyclic Sort In-Place	O(n)	O(1)	No	Yes	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly during interviews.

How to Present

Step 1: Clarify problem constraints and input range.Step 2: Explain brute force approach to show understanding.Step 3: Discuss sorting approach as an improvement.Step 4: Present optimal cyclic sort solution leveraging constraints.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Code: 10min → Testing & edge cases: 3min. Total ~20min

What the Interviewer Tests

Interviewers test your ability to leverage problem constraints, optimize time and space, and write clean, bug-free code.

Common Follow-ups

• What if numbers can appear more than twice? → Modify cyclic sort or use hash map.
• Can you solve without modifying the input array? → Use extra space like hash sets.

💡 These follow-ups test flexibility and understanding of tradeoffs between time, space, and input constraints.

🔍

Pattern Recognition

When to Use

1) Array contains numbers in range 1 to n; 2) Need to find duplicates or missing numbers; 3) Constraints allow in-place modification; 4) Linear time desired.

Signature Phrases

'Given an array of n integers where each integer is between 1 and n''Find all duplicates in the array''Without using extra space'

NOT This Pattern When

Problems requiring frequency counts without range constraints or problems needing hash maps for arbitrary values.

Similar Problems

Find the Missing Number - uses cyclic sort to find missing elementSet Mismatch - combines missing and duplicate detection using cyclic sort

Practice

1. You are given an unsorted array containing numbers from 1 to n with some numbers possibly missing or duplicated. The task is to rearrange the array so that each number i is placed at index i-1 if it exists. Which algorithmic approach guarantees an optimal O(n) time solution without extra sorting?

easy

A. Use cyclic sort by swapping elements to their correct indices based on their values until all are placed correctly.

B. Sort the array using a built-in sort function and then rearrange elements accordingly.

C. Use dynamic programming to track the placement of each number and build the sorted array.

D. Use a greedy approach that swaps elements to their correct positions until all are placed correctly.

Solution

1. Step 1: Understand the problem constraints

   The problem requires placing numbers 1 to n at indices 0 to n-1 respectively, handling duplicates or missing numbers efficiently.

2. Step 2: Identify the optimal approach

   Cyclic sort swaps elements to their correct positions in O(n) time without extra sorting or DP overhead, unlike greedy or sorting approaches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cyclic sort directly places elements by index in one pass [OK]

Hint: Cyclic sort swaps elements to correct indices in O(n) time [OK]

Common Mistakes:

• Confusing greedy swaps with cyclic sort
• Assuming sorting is always needed
• Misapplying DP to placement problems

2. You are given an array containing n distinct numbers taken from the range 0 to n. Exactly one number from this range is missing in the array. Which algorithmic approach guarantees finding the missing number in O(n) time and O(1) space without using extra data structures?

easy

A. Applying a dynamic programming approach to build a state table of present numbers

B. Sorting the array and then scanning for the missing number

C. Using a hash set to track presence of numbers and then checking which is missing

D. Cyclic sort to place each number at its correct index, then scanning for the mismatch

Solution

1. Step 1: Understand problem constraints

   The array contains numbers from 0 to n with one missing; all are distinct.

2. Step 2: Identify approach with O(n) time and O(1) space

   Cyclic sort places each number at its index in one pass, then a single scan finds the missing number efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cyclic sort rearranges in-place with linear time and constant space [OK]

Hint: Cyclic sort matches numbers to indices in-place [OK]

Common Mistakes:

• Assuming sorting is always O(n log n)
• Thinking hash sets use O(1) space
• Confusing DP with presence checking

3. You are given a sorted array of unique positive integers and a positive integer k. You need to find the kth positive integer that is missing from this array. Which algorithmic approach guarantees the most efficient solution in terms of time complexity?

easy

A. Use binary search on the array to find the position where the count of missing numbers reaches k.

B. Use a brute force linear scan counting missing numbers until the kth missing is found.

C. Use dynamic programming to store missing counts and find the kth missing number.

D. Use a greedy approach to iteratively guess missing numbers and verify their presence.

Solution

1. Step 1: Understand the problem constraints

   The array is sorted and contains unique positive integers. We want the kth missing positive number not in the array.

2. Step 2: Identify the optimal approach

   Binary search can be used to find the smallest index where the count of missing numbers is at least k, leveraging the formula missing = arr[mid] - (mid + 1). This yields O(log n) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search exploits sorted order and missing count formula [OK]

Hint: Binary search on missing count is optimal [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Confusing DP with missing count calculation

4. If the input array can contain numbers outside the range 1 to n (including negatives and zeros), which modification to the cyclic sort approach correctly finds all missing numbers in [1, n]?

hard

A. Ignore numbers outside 1 to n during swaps and only swap valid numbers

B. Use a hash set to track all numbers instead of cyclic sort

C. Replace invalid numbers with n+1 before cyclic sort to avoid errors

D. Sort the array first to bring valid numbers to front, then apply cyclic sort

Solution

1. Step 1: Identify invalid numbers impact

   Numbers outside 1 to n cause index errors or invalid swaps in cyclic sort.

2. Step 2: Modify cyclic sort to skip invalid numbers

   Only swap when nums[i] is in [1, n]; ignore or increment i otherwise to maintain O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring invalid numbers preserves cyclic sort correctness [OK]

Hint: Skip invalid numbers to avoid index errors [OK]

Common Mistakes:

• Using hash set loses O(1) space
• Replacing invalid numbers breaks uniqueness
• Sorting adds O(n log n) time

5. Suppose the problem changes: the array can contain repeated numbers that can be reused infinitely many times. Which modification to the optimal approach is necessary to correctly find the first k missing positive numbers?

hard

A. Use a frequency map instead of cyclic sort to track counts and find missing numbers.

B. Keep the cyclic sort but add a visited set to avoid infinite swaps due to reuse.

C. Replace cyclic sort with a brute force check for each number from 1 upwards until k missing are found.

D. Use a priority queue to generate missing numbers dynamically considering reuse.

Solution

1. Step 1: Understand reuse impact

   Infinite reuse means cyclic sort assumptions break because numbers can appear multiple times and be reused infinitely.

2. Step 2: Identify correct approach

   A frequency map tracks counts of each number, allowing detection of missing positives even with infinite reuse.

3. Step 3: Why other options fail

   Adding visited set won't prevent infinite swaps due to reuse. Brute force is inefficient. Priority queue adds overhead without correctness guarantee.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency map handles reuse correctly and efficiently [OK]

Hint: Reuse breaks cyclic sort; frequency map needed [OK]

Common Mistakes:

• Trying to patch cyclic sort with visited sets
• Assuming brute force is acceptable for large k
• Using priority queues unnecessarily