Find All Duplicates in Array

📋

Find All Duplicates in Array

Edge cases:

</>

IDE

def findDuplicates(nums: list[int]) -> list[int]:public List<Integer> findDuplicates(int[] nums)vector<int> findDuplicates(vector<int>& nums)function findDuplicates(nums)

def findDuplicates(nums):
    # Write your solution here
    pass

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> findDuplicates(vector<int>& nums) {
    // Write your solution here
    return {};
}

function findDuplicates(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [2]Only first duplicate detected; code stops early or misses others.✅ After cyclic sort, scan entire array to collect all duplicates, not just first found.

Wrong: [2,3,3]Duplicates reported multiple times due to lack of duplicate filtering.✅ Use a set or check duplicates only once per number before adding to result.

Wrong: [8]Misses duplicates at array end or non-adjacent duplicates.✅ Do not rely on sorting adjacency; use cyclic sort and full scan to find all duplicates.

Wrong: []Fails to detect duplicates due to incorrect index checks or missing post-processing.✅ After cyclic sort, check for elements not at their correct index and add them to duplicates.

Wrong: Timeout or no outputUsing nested loops brute force approach causing TLE on large inputs.✅ Implement O(n) cyclic sort with in-place swaps to avoid TLE.

✓

Test Cases

Focus on handling boundary cases like empty or single-element arrays.

Consider tricky cases where duplicates are repeated or non-adjacent.

Optimize your solution to O(n) time using cyclic sort to handle large inputs efficiently.

t1_01basic

Input{"nums":[4,3,2,7,8,2,3,1]}

Expected[2,3]

⏱ Performance - must finish in 2000ms

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

💡 Try placing each number at its correct index using cyclic sort.

💡 Check for numbers that are not at their correct index after sorting.

💡 Collect numbers that appear twice by identifying misplaced elements.

Why it failed: Output missing duplicates or extra numbers. Likely forgot to check all indices after cyclic sort. Fix by scanning array after placement to collect duplicates.

✓ Correctly identifies duplicates using cyclic sort and post-processing.

t1_02basic

Input{"nums":[1,1,2,3,4,5,6,7]}

Expected[1]

⏱ Performance - must finish in 2000ms

Only number 1 appears twice, all others once.

💡 Focus on detecting duplicates by comparing indices and values.

💡 Use cyclic sort to place numbers and then find duplicates by mismatch.

💡 Return all duplicates found after rearrangement.

Why it failed: Returned empty or incorrect duplicates list. Possibly missed checking all elements after sorting. Fix by iterating through entire array to find duplicates.

✓ Correctly returns the single duplicate after rearrangement.

t2_01edge

Input{"nums":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty array has no duplicates.

💡 Consider what happens when input array is empty.

💡 Your code should handle n=0 gracefully without errors.

💡 Return an empty list immediately if array is empty.

Why it failed: Code crashes or returns non-empty for empty input. Fix by adding a base case to return [] if input is empty.

✓ Handles empty input correctly by returning empty list.

t2_02edge

Input{"nums":[1]}

Expected[]

⏱ Performance - must finish in 2000ms

Single element array cannot have duplicates.

💡 Check behavior when array length is 1.

💡 No duplicates possible if only one element.

💡 Return empty list for single-element input.

Why it failed: Returns duplicates for single element input. Fix by ensuring duplicates require at least two occurrences.

✓ Correctly returns empty list for single element input.

t2_03edge

Input{"nums":[1,2,3,4,5,6,7,8,9,10]}

Expected[]

⏱ Performance - must finish in 2000ms

All elements unique, no duplicates.

💡 Test with all unique elements to confirm no false positives.

💡 After cyclic sort, all elements should be at correct indices.

💡 Return empty list if no duplicates found.

Why it failed: Returns duplicates when none exist. Fix by verifying duplicates only when element is misplaced and equals element at target index.

✓ Correctly returns empty list for all unique elements.

t2_04edge

Input{"nums":[2,2,3,4,5,6,7,8,9,9]}

Expected[2,9]

⏱ Performance - must finish in 2000ms

Duplicates appear at start and end of array.

💡 Check duplicates at both ends of the array.

💡 Cyclic sort must handle duplicates anywhere in array.

💡 Scan entire array after sorting to find duplicates.

Why it failed: Misses duplicates at array boundaries. Fix by scanning full array after cyclic sort to collect duplicates.

✓ Correctly identifies duplicates at array boundaries.

t3_01corner

Input{"nums":[2,2,2,2,2]}

Expected[2]

⏱ Performance - must finish in 2000ms

All elements are duplicates of 2, but only one duplicate reported.

💡 Check if your code handles multiple duplicates of the same number correctly.

💡 Remember problem states each integer appears once or twice, but test checks repeated duplicates.

💡 Ensure duplicates are reported once, even if repeated multiple times.

Why it failed: Returns multiple duplicates of same number or misses duplicates. Fix by using a set or checking duplicates only once per number.

✓ Correctly returns single duplicate 2 despite repeated duplicates.

t3_02corner

Input{"nums":[1,2,3,4,5,6,7,8,9,9,10,10]}

Expected[9,10]

⏱ Performance - must finish in 2000ms

Duplicates appear at the end of the array.

💡 Test if duplicates at array end are detected.

💡 Cyclic sort must handle duplicates anywhere in array.

💡 Check entire array after sorting to find duplicates.

Why it failed: Misses duplicates at the end of array. Fix by scanning full array after cyclic sort to collect duplicates.

✓ Correctly identifies duplicates at array end.

t3_03corner

Input{"nums":[1,2,3,4,5,6,7,8,8,9,10,10]}

Expected[8,10]

⏱ Performance - must finish in 2000ms

Duplicates appear non-consecutively and out of order.

💡 Duplicates may not be adjacent; do not rely on sorting alone.

💡 Use cyclic sort to place elements correctly and then find duplicates.

💡 Collect duplicates by checking if element is not at its correct index.

Why it failed: Fails to detect non-adjacent duplicates. Fix by using cyclic sort approach rather than sorting + adjacent check.

✓ Correctly finds non-adjacent duplicates.

t4_01performance

Input{"nums":[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37,37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46,47,47,48,48,49,49,50,50]}

Expected[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50]

⏱ Performance - must finish in 2000ms

n=100, O(n) cyclic sort must complete within 2s.

💡 Use O(n) cyclic sort to avoid TLE.

💡 Avoid nested loops which cause O(n^2) time.

💡 In-place swapping and single pass detection is key.

Why it failed: TLE due to nested loops or sorting approach. Fix by implementing O(n) cyclic sort with in-place swaps.

✓ Algorithm runs in O(n) time confirming efficiency.

Practice

1. Given the following code snippet, what is the output when the input array is [2, 3, 1, 5, 3]?

def find_duplicate_missing(nums):
    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:
            return [nums[i], i + 1]
    return [-1, -1]

print(find_duplicate_missing([2, 3, 1, 5, 3]))

easy

A. [3, 5]

B. [5, 4]

C. [3, 4]

D. [2, 4]

Solution

1. Step 1: Trace swaps in the while loop

   Initial array: [2,3,1,5,3] - i=0: nums[0]=2, correct_index=1, swap nums[0] and nums[1] -> [3,2,1,5,3] - i=0: nums[0]=3, correct_index=2, swap nums[0] and nums[2] -> [1,2,3,5,3] - i=0: nums[0]=1, correct_index=0, nums[0]==nums[correct_index], i=1 - i=1: nums[1]=2, correct_index=1, nums[1]==nums[correct_index], i=2 - i=2: nums[2]=3, correct_index=2, nums[2]==nums[correct_index], i=3 - i=3: nums[3]=5, correct_index=4, swap nums[3] and nums[4] -> [1,2,3,3,5] - i=3: nums[3]=3, correct_index=2, nums[3]==nums[correct_index], i=4 - i=4: nums[4]=5, correct_index=4, nums[4]==nums[correct_index], i=5 (exit loop)

2. Step 2: Identify mismatch in second loop

   Check indices: - i=0: nums[0]=1 correct - i=1: nums[1]=2 correct - i=2: nums[2]=3 correct - i=3: nums[3]=3 incorrect, expected 4 -> duplicate=3, missing=4 Return [3,4]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected duplicate and missing [OK]

Hint: Trace swaps carefully to find final array mismatch [OK]

Common Mistakes:

• Confusing duplicate and missing values
• Off-by-one errors in indexing
• Stopping swaps too early

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. Consider the following buggy code for finding the duplicate number. Which line contains the subtle bug that can cause an infinite loop or incorrect result?

medium

A. Line 7: else: i += 1

B. Line 4: if nums[i] == nums[correct_index]:

C. Line 9: else: nums[i], nums[correct_index] = nums[correct_index], nums[i]

D. Line 2: while i < len(nums):

Solution

1. Step 1: Compare with correct code condition

   The condition should be if nums[i] != nums[correct_index] to decide when to swap.

2. Step 2: Identify effect of wrong condition

   Using == causes swapping only when elements are equal, leading to infinite loops or missed duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Incorrect condition breaks cyclic sort logic [OK]

Hint: Swap only when elements differ, not when equal [OK]

Common Mistakes:

• Reversing the swap condition causing infinite loops
• Incrementing index incorrectly
• Swapping elements in wrong order

4. Consider the following buggy implementation of the cyclic sort approach to find the smallest missing positive range. Identify the line that contains the subtle bug causing incorrect results or infinite loops.

def find_smallest_missing_range(nums):
    n = len(nums)
    i = 0
    while i < n:
        correct_pos = nums[i] - 1
        if 1 <= nums[i] <= n and nums[i] != nums[correct_pos]:
            nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
            # Missing increment of i here
        else:
            i += 1
    start = 1
    for i in range(n):
        if nums[i] != i + 1:
            start = i + 1
            break
    else:
        return [n + 1, n + 1]
    end = start
    while end <= n and nums[end - 1] != end:
        end += 1
    return [start, end - 1]

medium

A. Line missing increment of i after swap inside the while loop

B. Line with the swap: nums[i], nums[correct_pos] = nums[correct_pos], nums[i]

C. Line checking if nums[i] != i + 1 in the for loop

D. Line returning [n + 1, n + 1] if no missing range found

Solution

1. Step 1: Identify the infinite loop cause

   After swapping, the index i is not incremented, so the same index is checked repeatedly causing infinite loop.

2. Step 2: Confirm other lines are correct

   Swap line correctly swaps elements; the for loop and return lines handle missing range detection properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing i increment after swap causes infinite loop or incorrect behavior [OK]

Hint: Always increment index after swap or carefully control loop [OK]

Common Mistakes:

• Forgetting to increment i after swap
• Misplacing swap condition

5. The following code attempts to find the kth missing positive number using binary search. Which line contains a subtle bug that causes incorrect results when the kth missing number is less than the first element of the array?

medium

A. Line 6: if missing <= k:

B. Line 4: mid = (low + high) // 2

C. Line 8: low = mid + 1

D. Line 10: return k + high + 1

Solution

1. Step 1: Identify the bug in condition

   The condition uses <= instead of < when comparing missing and k. This causes the binary search to move low pointer incorrectly when missing equals k.

2. Step 2: Explain impact on edge cases

   When kth missing is less than arr[0], missing counts start at zero, and using <= causes the search to skip the correct boundary, returning wrong results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing <= to < fixes boundary handling [OK]

Hint: Check strict inequality in binary search condition [OK]

Common Mistakes:

• Using <= instead of <
• Incorrect return formula