Problem Description

You are given an integer array nums with length n. The array has these specific properties:

• All integers in the array are within the range [1, n] (inclusive)
• Each integer appears either once or twice (at most twice)

Your task is to find and return all integers that appear exactly twice in the array.

The challenge comes with two important constraints:

1. Time Complexity: Your algorithm must run in O(n) time, meaning it should make a linear pass through the array
2. Space Complexity: You can only use constant auxiliary space O(1), not counting the space needed for the output array

For example:

• If nums = [4,3,2,7,8,2,3,1], the output should be [2,3] because 2 and 3 appear twice
• If nums = [1,1,2], the output should be [1] because only 1 appears twice

The key insight for solving this problem is to leverage the fact that all numbers are in the range [1, n], which means we can use the array indices (which go from 0 to n-1) to track information about the numbers themselves.

Intuition

Since we need O(1) space and can't use a separate data structure to track duplicates, we need to be creative with the given array itself. The key observation is that the numbers range from 1 to n, and we have array indices from 0 to n-1. This creates a natural mapping: each number x can correspond to index x-1.

The idea is to place each number at its "correct" position - number 1 should be at index 0, number 2 should be at index 1, and so on. If we try to place a number at its correct position and find that the same number is already there, we've found a duplicate.

Think of it like organizing numbered balls into numbered slots:

• Ball #1 goes into slot #0
• Ball #2 goes into slot #1
• And so on...

When we encounter a ball that wants to go into a slot that already has the same numbered ball, we know we have a duplicate. But instead of immediately recording it as a duplicate, we continue the sorting process.

The algorithm uses a cyclic sort approach. For each position, we keep swapping the current number with the number at its target position until either:

1. The current number is already in its correct position, or
2. The target position already contains the same number (indicating a duplicate)

After this sorting process, we scan through the array. Any position i that doesn't contain the value i+1 means that i+1 is missing, and the value actually at position i must be a duplicate (since it couldn't go to its correct position).

For example, if after sorting we have [1, 2, 3, 3, 5]:

• Index 3 contains 3 instead of 4
• This tells us that 3 appears twice (once at its correct position 2, and once here at position 3)

Solution Approach

The solution implements a cyclic sort algorithm to place each number at its correct position (number i at index i-1). Let's walk through the implementation step by step:

Step 1: Cyclic Sort

for i in range(len(nums)):
    while nums[i] != nums[nums[i] - 1]:
        nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

For each position i, we check if the current number is at its correct position:

• The number at index i should ideally go to index nums[i] - 1
• We keep swapping until either:
  • The current number reaches its correct position, or
  • We find that the target position already has the same number (duplicate case)

The condition nums[i] != nums[nums[i] - 1] checks:

• Is the number at position i different from the number at its target position?
• If yes, swap them
• If no, either it's already in the correct position or it's a duplicate

Example walkthrough with [4,3,2,7,8,2,3,1]:

• At i=0: nums[0]=4 should go to index 3. Swap with nums[3]=7
• Now nums[0]=7 should go to index 6. Swap with nums[6]=3
• Now nums[0]=3 should go to index 2. Swap with nums[2]=2
• Now nums[0]=2 should go to index 1. Swap with nums[1]=3
• Now nums[0]=3 wants to go to index 2, but nums[2]=3 already. Stop.
• Continue this process for all positions...

Step 2: Identify Duplicates

return [v for i, v in enumerate(nums) if v != i + 1]

After sorting, scan through the array:

• At each index i, check if nums[i] == i + 1
• If not, then nums[i] is a duplicate (it couldn't go to its correct position because another copy is already there)
• The value at this position is one of our duplicates

Time Complexity: O(n) - Although we have nested loops, each element is moved at most once to its correct position.

Space Complexity: O(1) - We only use the input array itself for sorting, no extra space except for the output array.

Example Walkthrough

Let's walk through a small example with nums = [3, 1, 3, 2] to illustrate the cyclic sort approach.

Initial array: [3, 1, 3, 2]

Step 1: Cyclic Sort Process

Position i=0:

• Current value: nums[0] = 3
• Target position for 3: index 3-1 = 2
• Check condition: nums[0] != nums[2] → 3 != 3 → False
• Since the target position already has 3, we stop swapping
• Array remains: [3, 1, 3, 2]

Position i=1:

• Current value: nums[1] = 1
• Target position for 1: index 1-1 = 0
• Check condition: nums[1] != nums[0] → 1 != 3 → True
• Swap nums[1] with nums[0]: [1, 3, 3, 2]
• Now nums[1] = 3, target position: index 2
• Check condition: nums[1] != nums[2] → 3 != 3 → False
• Stop swapping (duplicate found)
• Array: [1, 3, 3, 2]

Position i=2:

• Current value: nums[2] = 3
• Target position for 3: index 3-1 = 2
• Check condition: nums[2] != nums[2] → 3 != 3 → False
• Already in correct position
• Array: [1, 3, 3, 2]

Position i=3:

• Current value: nums[3] = 2
• Target position for 2: index 2-1 = 1
• Check condition: nums[3] != nums[1] → 2 != 3 → True
• Swap nums[3] with nums[1]: [1, 2, 3, 3]
• Now nums[3] = 3, target position: index 2
• Check condition: nums[3] != nums[2] → 3 != 3 → False
• Stop swapping (duplicate found)
• Final array: [1, 2, 3, 3]

Step 2: Identify Duplicates

After sorting, we have: [1, 2, 3, 3]

Now we scan through each position:

• Index 0: nums[0] = 1, expected 0+1 = 1 ✓ (correct)
• Index 1: nums[1] = 2, expected 1+1 = 2 ✓ (correct)
• Index 2: nums[2] = 3, expected 2+1 = 3 ✓ (correct)
• Index 3: nums[3] = 3, expected 3+1 = 4 ✗ (mismatch!)

At index 3, we found 3 instead of 4. This means:

• Number 4 is missing from the array
• Number 3 appears twice (once at its correct position 2, once here at position 3)

Result: [3] - the number 3 appears twice in the original array.

The beauty of this approach is that duplicates naturally end up at positions where they don't belong, making them easy to identify in the final scan.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses cyclic sort to place each number at its correct position (number i should be at index i-1). Although there's a nested while loop inside the for loop, each element is moved at most once to its correct position.

• The outer for loop runs n times
• The inner while loop swaps elements to their correct positions, but each element is visited/swapped at most twice throughout the entire algorithm execution (once when encountered in the for loop, and potentially once more when being swapped to its correct position)
• The list comprehension at the end runs through all n elements once

Therefore, the total operations are bounded by O(n) + O(n) = O(n).

Space Complexity: O(1)

The algorithm modifies the input array in-place and only uses a constant amount of extra space:

• The loop variable i takes O(1) space
• The swapping operation uses implicit temporary variables but still O(1) space
• The returned list containing duplicates is not counted as extra space since it's the required output

The space complexity is O(1) excluding the space needed for the output array.

Common Pitfalls

1. Index Calculation Error in the While Loop Condition

The Pitfall: A common mistake is incorrectly writing the while loop condition or the swap operation, which can lead to infinite loops or index out of bounds errors. For example:

# WRONG - This can cause infinite loop
while nums[i] != i + 1:
    nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

The problem with this approach is that it tries to sort ALL elements to their correct positions, but when duplicates exist, this becomes impossible and creates an infinite loop.

The Solution: The correct condition should check if the current element is different from the element at its target position:

# CORRECT
while nums[i] != nums[nums[i] - 1]:
    nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

This ensures the loop terminates when either:

• The element reaches its correct position, OR
• A duplicate is detected (same value already exists at the target position)

2. Incorrect Swap Implementation

The Pitfall: Using temporary variables or incorrect order in simultaneous assignment can corrupt the data:

# WRONG - nums[i] gets modified before being used on the right side
nums[nums[i] - 1] = nums[i]
nums[i] = nums[nums[i] - 1]  # This uses the already modified nums[nums[i] - 1]

The Solution: Use Python's simultaneous assignment which evaluates all expressions on the right side before any assignment:

# CORRECT
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

Alternatively, if using a language without simultaneous assignment, store the index first:

# ALSO CORRECT
correct_idx = nums[i] - 1
temp = nums[correct_idx]
nums[correct_idx] = nums[i]
nums[i] = temp

3. Misunderstanding the Final Check Logic

The Pitfall: After cyclic sort, developers might incorrectly identify duplicates by checking for sorted order rather than checking if each element is at its "home" position:

# WRONG - This assumes the array should be sorted [1,2,3,...,n]
duplicates = []
for i in range(1, len(nums)):
    if nums[i] == nums[i-1]:  # Looking for consecutive duplicates
        duplicates.append(nums[i])

The Solution: Remember that after cyclic sort with duplicates, the array won't be perfectly sorted. Instead, check if each element is at its correct index (value v should be at index v-1):

# CORRECT
duplicates = []
for i in range(len(nums)):
    if nums[i] != i + 1:  # Element at index i should be i+1
        duplicates.append(nums[i])

4. Not Handling Edge Cases

The Pitfall: Not considering arrays where all elements are unique or all elements are the same:

# Missing edge case handling
nums = [1, 1, 1, 1]  # All same elements
nums = [1, 2, 3, 4]  # All unique elements

The Solution: The cyclic sort approach naturally handles these cases:

• For all unique elements: Each element goes to its home position, and the final check finds no duplicates
• For all same elements: After the first element is placed, all subsequent swaps are skipped (due to the while condition), and the final check correctly identifies the duplicates

The algorithm works correctly without special case handling, but it's important to test these scenarios to ensure correctness.