Problem

In the town of Digitville, there was a list of numbers called nums containing integers from 0 to n - 1. Each number was supposed to appear exactly once in the list, however, two mischievous numbers sneaked in an additional time , making the list longer than usual.

As the town detective, your task is to find these two sneaky numbers. Return an array of size two containing the two numbers (in any order), so peace can return to Digitville.

Examples

Example 1

1
2
3
4
5
6
7
8


Input: nums = [0,1,1,0]

Output: [0,1]

Explanation:

The numbers 0 and 1 each appear twice in the array.

Example 2

1
2
3
4
5
6
7
8


Input: nums = [0,3,2,1,3,2]

Output: [2,3]

Explanation:

The numbers 2 and 3 each appear twice in the array.

Example 3

1
2
3
4
5
6
7
8


Input: nums = [7,1,5,4,3,4,6,0,9,5,8,2]

Output: [4,5]

Explanation:

The numbers 4 and 5 each appear twice in the array.

Constraints

  • 2 <= n <= 100
  • nums.length == n + 2
  • 0 <= nums[i] < n
  • The input is generated such that nums contains exactly two repeated elements.

Solution

Method 1 - Count Occurrences

We count the occurrences of each number using a hash table or array. The two numbers that appear twice are the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <vector>
using namespace std;
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        vector<int> cnt(n, 0), res;
        for (int x : nums) ++cnt[x];
        for (int i = 0; i < n; ++i) if (cnt[i] == 2) res.push_back(i);
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import java.util.*;
class Solution {
    public int[] findDuplicates(int[] nums) {
        int n = nums.length;
        int[] cnt = new int[n];
        for (int x : nums) cnt[x]++;
        int[] res = new int[2];
        int idx = 0;
        for (int i = 0; i < n; ++i) if (cnt[i] == 2) res[idx++] = i;
        return res;
    }
}
1
2
3
4
5
6

from typing import List
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        from collections import Counter
        count = Counter(nums)
        return [x for x in count if count[x] == 2]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

use std::collections::HashMap;
impl Solution {
    pub fn find_duplicates(nums: Vec<i32>) -> Vec<i32> {
        let mut count = std::collections::HashMap::new();
        for &x in &nums {
            *count.entry(x).or_insert(0) += 1;
        }
        count.into_iter().filter(|&(_, v)| v == 2).map(|(k, _)| k).collect()
    }
}
1
2
3
4
5

function findDuplicates(nums: number[]): number[] {
    const count = new Map<number, number>();
    for (const x of nums) count.set(x, (count.get(x) ?? 0) + 1);
    return Array.from(count.entries()).filter(([k, v]) => v === 2).map(([k]) => k);
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)