Problem

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Examples

Example 1:

1
2
3
4

Input:
nums = [4,3,2,7,8,2,3,1]
Output:
 [2,3]

Example 2:

1
2
3
4

Input:
nums = [1,1,2]
Output:
 [1]

Example 3:

1
2
3
4

Input:
nums = [1]
Output:
 []

Solution

Method 1 – Cyclic Sort for In-Place Duplicate Detection

Intuition

Since all numbers are in the range [1, n], we can use the array indices to place each number at its correct position (i.e., value v at index v-1). If a number is already at its correct position or a duplicate is found, we skip it. This way, duplicates will be left at positions where the value does not match the index + 1.

Approach

  1. Iterate through the array and for each index i, while nums[i] != nums[nums[i] - 1], swap nums[i] with nums[nums[i] - 1].
  2. After the swaps, iterate through the array again. If nums[i] != i + 1, then nums[i] is a duplicate.
  3. Collect all such duplicates in a result list and return it.

Complexity

  • ⏰ Time complexity: O(n), as each element is swapped at most once.
  • 🧺 Space complexity: O(1), since the algorithm works in-place and uses only a result list for output.

Code

1
2


##### C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) ans.push_back(nums[i]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func findDuplicates(nums []int) []int {
    n := len(nums)
    for i := 0; i < n; i++ {
        for nums[i] != nums[nums[i]-1] {
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        }
    }
    ans := []int{}
    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            ans = append(ans, nums[i])
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] != nums[nums[i] - 1]) {
                int tmp = nums[i];
                nums[i] = nums[tmp - 1];
                nums[tmp - 1] = tmp;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) ans.add(nums[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7

class Solution:
    def findDuplicates(self, nums: list[int]) -> list[int]:
        n = len(nums)
        for i in range(n):
            while nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        return [v for i, v in enumerate(nums) if v != i + 1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun findDuplicates(nums: IntArray): List<Int> {
        val n = nums.size
        for (i in 0 until n) {
            while (nums[i] != nums[nums[i] - 1]) {
                val tmp = nums[i]
                nums[i] = nums[tmp - 1]
                nums[tmp - 1] = tmp
            }
        }
        val ans = mutableListOf<Int>()
        for (i in 0 until n) {
            if (nums[i] != i + 1) ans.add(nums[i])
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

function findDuplicates(nums: number[]): number[] {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        while (nums[i] !== nums[nums[i] - 1]) {
            const tmp = nums[i];
            nums[i] = nums[tmp - 1];
            nums[tmp - 1] = tmp;
        }
    }
    const ans: number[] = [];
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) ans.push(nums[i]);
    }
    return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn find_duplicates(nums: &mut Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        for i in 0..n {
            while nums[i] != nums[(nums[i] - 1) as usize] {
                let j = (nums[i] - 1) as usize;
                nums.swap(i, j);
            }
        }
        let mut ans = Vec::new();
        for (i, &v) in nums.iter().enumerate() {
            if v != (i as i32) + 1 {
                ans.push(v);
            }
        }
        ans
    }
}