Find All Duplicates in Array

▶

Steps

setup

Initialize variables

We start with the input array and initialize an empty list for duplicates and the index pointer i at 0.

💡 Setting up the initial state is crucial to track progress and store results.

Line:

duplicates = []
i = 0
n = len(nums)

💡 We have a pointer i ready to scan the array and a place to collect duplicates.

compare

Calculate correct index for nums[i]

At index i=0, the current number is 4. We calculate its correct index as 3 (4 - 1).

💡 Finding the correct index helps us know where this number should be placed.

Line:

correct_index = nums[i] - 1

💡 Each number belongs at index equal to its value minus one.

compare

Check if swap needed at i=0

We compare nums[i]=4 with nums[correct_index]=7. Since they differ, we swap them to move 4 closer to its correct position.

💡 Swapping places the current number where it belongs, progressing the sort.

Line:

if nums[i] != nums[correct_index]:
    nums[i], nums[correct_index] = nums[correct_index], nums[i]

💡 Swapping moves numbers closer to their correct indices, reducing disorder.

compare

Recalculate correct index for new nums[i]

After swap, nums[i]=7 at index 0. We calculate its correct index as 6 (7 - 1).

💡 We must check if the new number at i=0 is at its correct position or needs swapping.

Line:

correct_index = nums[i] - 1

💡 Each iteration tries to place the current number correctly before moving on.

swap

Swap nums[i] with nums[correct_index]

nums[i]=7 differs from nums[correct_index]=3, so we swap them to move 7 closer to its correct position.

💡 Swapping continues until the current number is at its correct index or a duplicate is detected.

Line:

if nums[i] != nums[correct_index]:
    nums[i], nums[correct_index] = nums[correct_index], nums[i]

💡 Repeated swaps at the same index place multiple numbers correctly in sequence.

compare

Recalculate correct index for new nums[i]

Now nums[i]=3 at index 0. Its correct index is 2 (3 - 1).

💡 We check if this new number is at its correct position or needs swapping.

Line:

correct_index = nums[i] - 1

💡 The algorithm keeps trying to place the current number correctly before moving on.

swap

Swap nums[i] with nums[correct_index]

nums[i]=3 differs from nums[correct_index]=2, so we swap them to move 3 closer to its correct position.

💡 Swapping continues until the current number is at its correct index or a duplicate is detected.

Line:

if nums[i] != nums[correct_index]:
    nums[i], nums[correct_index] = nums[correct_index], nums[i]

💡 Each swap places one number correctly, reducing disorder.

compare

Recalculate correct index for new nums[i]

Now nums[i]=2 at index 0. Its correct index is 1 (2 - 1).

💡 We check if this new number is at its correct position or needs swapping.

Line:

correct_index = nums[i] - 1

💡 The algorithm tries to place the current number correctly before moving on.

compare

Check if swap needed at i=0

nums[i]=2 differs from nums[correct_index]=3, so we swap to place 2 at its correct index.

💡 We swap to place 2 at its correct index.

Line:

if nums[i] != nums[correct_index]:
    nums[i], nums[correct_index] = nums[correct_index], nums[i]

💡 Swapping moves numbers closer to their correct positions.

compare

Recalculate correct index for new nums[i]

Now nums[i]=3 at index 0. Its correct index is 2 (3 - 1).

💡 We check if this new number is at its correct position or needs swapping.

Line:

correct_index = nums[i] - 1

💡 The algorithm tries to place the current number correctly before moving on.

compare

Check for duplicate to avoid infinite swap

nums[i]=3 equals nums[correct_index]=3, so no swap is done and we move i forward.

💡 Detecting duplicates prevents infinite swapping loops.

Line:

else:
    i += 1

💡 Duplicates cause the algorithm to advance the pointer instead of swapping.

compare

Process i=1: calculate correct index

At i=1, nums[i]=2. Its correct index is 1 (2 - 1).

💡 Check if the current number is at its correct position.

Line:

correct_index = nums[i] - 1

💡 If the number is already at the correct index, move on.

move_right

No swap needed, move i forward

nums[i]=2 equals nums[correct_index]=2, so we increment i to 2.

💡 When the number is at the correct index, we proceed to the next element.

Line:

else:
    i += 1

💡 Correctly placed numbers are skipped.

compare

Process i=2: calculate correct index

At i=2, nums[i]=3. Its correct index is 2 (3 - 1).

💡 Check if the current number is at its correct position.

Line:

correct_index = nums[i] - 1

💡 If the number is already at the correct index, move on.

move_right

No swap needed, move i forward

nums[i]=3 equals nums[correct_index]=3, so we increment i to 3.

💡 When the number is at the correct index, we proceed to the next element.

Line:

else:
    i += 1

💡 Correctly placed numbers are skipped.

traverse

Continue cyclic sort until i reaches end

The algorithm continues this process for i=3 to i=7, swapping or moving forward as needed to place numbers correctly.

💡 This repetitive process ensures all numbers are placed or duplicates detected.

Line:

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

💡 The cyclic sort loop rearranges the array in-place efficiently.

traverse

Start collecting duplicates

We iterate through the array to find elements not at their correct index, indicating duplicates.

💡 Numbers not at their correct index are duplicates because their correct position is occupied.

Line:

for i in range(n):
    if nums[i] != i + 1:
        duplicates.append(nums[i])

💡 Duplicates appear as misplaced numbers after cyclic sort.

insert

Add duplicate 3 to duplicates list

Since nums[4]=3 is not equal to 5 (index+1), we add 3 to duplicates.

💡 This confirms 3 appears more than once.

Line:

duplicates.append(nums[i])

💡 Duplicates are detected by mismatch between value and index+1.

insert

Add duplicate 2 to duplicates list

Since nums[5]=2 is not equal to 6 (index+1), we add 2 to duplicates.

💡 This confirms 2 appears more than once.

Line:

duplicates.append(nums[i])

💡 Duplicates are identified by their incorrect positions after sorting.

reconstruct

Return duplicates list

The algorithm returns the duplicates list [2, 3] as the final answer.

💡 Returning the collected duplicates completes the problem solution.

Line:

return duplicates

💡 The duplicates list contains all numbers appearing more than once.

def findDuplicates(nums):
    duplicates = []  # STEP 1
    i = 0  # STEP 1
    n = len(nums)  # STEP 1
    while i < n:  # STEP 16
        correct_index = nums[i] - 1  # STEPS 2,4,6,8,10,12,14
        if nums[i] != nums[correct_index]:  # STEPS 3,5,7,9
            nums[i], nums[correct_index] = nums[correct_index], nums[i]  # STEPS 3,5,7,9
        else:
            i += 1  # STEPS 11,13,15
    for i in range(n):  # STEP 17
        if nums[i] != i + 1:  # STEPS 17,18,19
            duplicates.append(nums[i])  # STEPS 18,19
    return duplicates  # STEP 20

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

📊

Find All Duplicates in Array - Watch the Algorithm Execute, Step by Step

Watching each swap and pointer movement reveals how cyclic sort efficiently organizes elements and detects duplicates without extra space.

setup

i

4

0

3

1

2

2

7

3

8

4

2

5

3

6

1

7

Result: []

compare

i

4

0

3

1

2

2

correct_index

7

3

8

4

2

5

3

6

1

7

Result: []

swap

i

7

0

3

1

2

2

correct_index

4

3

8

4

2

5

3

6

1

7

Result: []

compare

i

7

0

3

1

2

2

4

3

8

4

2

5

correct_index

3

6

1

7

Result: []

swap

i

3

0

3

1

2

2

4

3

8

4

2

5

correct_index

7

6

1

7

Result: []

compare

i

3

0

3

1

correct_index

2

2

4

3

8

4

2

5

7

6

1

7

Result: []

swap

i

2

0

3

1

correct_index

3

2

4

3

8

4

2

5

7

6

1

7

Result: []

compare

i

2

0

correct_index

3

1

3

2

4

3

8

4

2

5

7

6

1

7

Result: []

swap

i

3

0

correct_index

2

1

3

2

4

3

8

4

2

5

7

6

1

7

Result: []

compare

i

3

0

2

1

correct_index

3

2

4

3

8

4

2

5

7

6

1

7

Result: []

move_right

3

0

i

2

1

3

2

4

3

8

4

2

5

7

6

1

7

Result: []

compare

3

0

correct_index

2

1

3

2

4

3

8

4

2

5

7

6

1

7

Result: []

move_right

3

0

2

1

i

3

2

4

3

8

4

2

5

7

6

1

7

Result: []

compare

3

0

2

1

correct_index

3

2

4

3

8

4

2

5

7

6

1

7

Result: []

move_right

3

0

2

1

3

2

i

4

3

8

4

2

5

7

6

1

7

Result: []

traverse

1

0

2

1

3

2

4

3

3

4

2

5

7

6

8

7

Result: []

compare

1

0

2

1

3

2

4

3

i

3

4

2

5

7

6

8

7

Result: []

insert

1

0

2

1

3

2

4

3

3

4

i

2

5

7

6

8

7

Result: [3]

insert

1

0

2

1

3

2

4

3

3

4

2

5

7

6

8

7

Result: [3,2]

record

1

0

2

1

3

2

4

3

3

4

2

5

7

6

8

7

Result: [2,3]

Key Takeaways

✓ Cyclic sort places each number at its correct index, enabling easy detection of duplicates by checking misplaced elements.

This insight is hard to see from code alone because the in-place swaps and pointer logic are subtle without visualization.

✓ Duplicates cause the algorithm to skip swapping and move forward, preventing infinite loops.

Understanding this branching is easier when watching the pointer movement and swap decisions step-by-step.

✓ After sorting, duplicates appear as numbers not matching their index+1, which is a simple and efficient way to identify them.

This final scan is a key step that is easy to overlook when reading code but clear in the visualization.

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 of n + 1 integers where each integer is between 1 and n (inclusive). Exactly one number is duplicated but may appear multiple times. Which approach guarantees finding the duplicate in O(n) time and O(1) space without modifying the input array?

easy

A. Using a cycle detection algorithm like Floyd's Tortoise and Hare

B. Sorting the array and then scanning for adjacent duplicates

C. Using a hash set to track seen numbers

D. Nested loops comparing every pair of elements

Solution

1. Step 1: Understand problem constraints

   The array contains n+1 integers with values from 1 to n, guaranteeing at least one duplicate and a cycle in the value-to-index mapping.

2. Step 2: Identify approach that works without modifying input and uses O(1) space

   Cycle detection (Floyd's Tortoise and Hare) exploits the cycle formed by duplicates and finds the duplicate in linear time and constant space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detection fits constraints perfectly [OK]

Hint: Cycle detection finds duplicates without modifying input [OK]

Common Mistakes:

• Assuming sorting is always optimal despite input modification constraints
• Using nested loops which are O(n²)
• Using extra space with hash sets when O(1) space is required

3. You are given an unsorted integer array and need to find the smallest positive integer missing from it in O(n) time and O(1) extra space. Which algorithmic approach best guarantees this optimal solution?

easy

A. Sorting the array and then scanning for the first missing positive

B. Applying a greedy approach to pick the smallest missing positive at each step

C. Using a hash set to track presence of numbers and then scanning from 1 upwards

D. Placing each number in its correct index position using cyclic sort and then scanning

Solution

1. Step 1: Understand the problem constraints

   The problem requires O(n) time and O(1) space, which rules out sorting (O(n log n)) and hash sets (O(n) space).

2. Step 2: Identify the approach that rearranges elements in-place

   Cyclic sort places each number in its correct index (number k at index k-1), enabling a linear scan to find the first missing positive efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cyclic sort achieves O(n) time and O(1) space [OK]

Hint: Optimal solution uses in-place cyclic sort [OK]

Common Mistakes:

• Choosing sorting which is O(n log n)
• Using hash sets which use extra space
• Greedy approaches that don't guarantee correctness

4. Consider this buggy code snippet for finding missing numbers. Which line contains the subtle bug that can cause infinite loops or incorrect output?

medium

A. Line 3: wrong initialization of n

B. Line 7: incorrect increment of i

C. Line 9: appending missing numbers incorrectly

D. Line 5: missing check before swapping

Solution

1. Step 1: Identify the missing condition before swap

   The code swaps unconditionally without checking if nums[i] == nums[correct], causing infinite swaps when duplicates exist.

2. Step 2: Confirm other lines are correct

   Incrementing i only happens in else, missing numbers appended correctly, and n initialized properly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing condition before swap causes infinite loop or wrong placement [OK]

Hint: Check swap condition to avoid infinite loops [OK]

Common Mistakes:

• Forgetting duplicate check before swap
• Incrementing i incorrectly
• Appending indices instead of values

5. Suppose the input array can contain numbers outside the range 1 to n, including negatives and zeros, and duplicates. Which modification to the cyclic sort algorithm ensures correct placement of numbers 1 to n at indices 0 to n-1 while ignoring invalid numbers?

hard

A. Swap elements only if arr[i] is in [1, n] and arr[i] != arr[arr[i] - 1], else increment i.

B. Use an extra array of size n to place valid numbers at index num-1, ignoring invalids.

C. Sort the array first, then remove invalid numbers and duplicates.

D. Ignore duplicates by skipping swaps when arr[i] == arr[arr[i] - 1] without checking range.

Solution

1. Step 1: Understand input constraints

   Input may have invalid numbers (negatives, zeros, > n) and duplicates that break in-place cyclic sort.

2. Step 2: Use extra array for placement

   Creating a separate array of size n and placing valid numbers at index num-1 ensures correct placement ignoring invalids and duplicates.

3. Step 3: Avoid in-place swaps that cause index errors or infinite loops

   Extra space approach is safer and simpler for this variant.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Extra array handles invalid and duplicate numbers cleanly [OK]

Hint: Extra array avoids invalid index and duplicate issues [OK]

Common Mistakes:

• Ignoring invalid range checks
• Trying to fix in-place swaps with invalid numbers
• Not handling duplicates properly