# The Two Sneaky Numbers of Digitville
**Difficulty:** EASY
[External](https://leetcode.com/problems/the-two-sneaky-numbers-of-digitville)
Canonical: https://scaleengineer.com/dsa/problems/the-two-sneaky-numbers-of-digitville
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, Hash Table
---
## 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.

**Example 1:**

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

**Output:** \[0,1\]

**Explanation:**

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

**Example 2:**

**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:**

**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.

# Approaches
## Brute Force with Nested Loops
The most straightforward, yet least efficient, way to solve this problem is by using a brute-force approach. We can compare every number in the array with every other number to find pairs that are identical. This involves using two nested loops.
**Time:** O(N^2), where N is the number of elements in `nums`. For each element, we iterate through the rest of the array, leading to a quadratic number of comparisons. · **Space:** O(1) auxiliary space. The `Set` used for storing the duplicates will hold at most two elements, which is constant space.
**Pros:** Simple to understand and implement.; Uses constant extra space (as the result set size is fixed at 2).
**Cons:** Extremely inefficient for larger arrays due to its quadratic time complexity.; Likely to result in a 'Time Limit Exceeded' error on most coding platforms for non-trivial input sizes.
### Explanation
In this method, we take each element of the array and scan the rest of the array to see if a duplicate of that element exists. We use a `Set` to store the found duplicates, which conveniently handles the issue of finding the same duplicate pair multiple times. For example, in `[1, 1, 1]`, comparing the first and second `1`s finds a duplicate, and comparing the first and third `1`s finds the same duplicate. The set ensures we only store `1` once.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] findTwoSneakyNumbers(int[] nums) {
        Set<Integer> duplicates = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    duplicates.add(nums[i]);
                }
            }
        }
        
        int[] result = new int[duplicates.size()];
        int index = 0;
        for (int num : duplicates) {
            result[index++] = num;
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty `Set` called `duplicates` to store the results and avoid adding the same number twice.
- Use a nested loop structure. The outer loop iterates from `i = 0` to `nums.length - 1`.
- The inner loop iterates from `j = i + 1` to `nums.length - 1`.
- Inside the inner loop, compare `nums[i]` and `nums[j]`.
- If `nums[i] == nums[j]`, it signifies a duplicate. Add `nums[i]` to the `duplicates` set.
- After the loops complete, convert the `duplicates` set into an array and return it.

## Sorting the Array
A more efficient approach involves sorting the array first. Once the array is sorted, any duplicate numbers will be grouped together, making them easy to identify in a single pass.
**Time:** O(N log N), where N is the length of the array. The sorting step is the bottleneck. · **Space:** O(log N) to O(N), depending on the sorting algorithm. Java's `Arrays.sort()` for primitive types uses a variant of Quicksort, which requires O(log N) space on average.
**Pros:** A significant improvement over the brute-force approach.; Relatively easy to implement using built-in sorting functions.
**Cons:** The time complexity is dominated by the sorting algorithm, which is not as efficient as linear-time solutions.; The space complexity depends on the sorting algorithm's implementation, which might not be O(1).
### Explanation
By sorting the array, we ensure that identical elements become adjacent. We can then iterate through the sorted array and check if an element is the same as the one immediately following it. If they are the same, we've found one of the sneaky numbers.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[] findTwoSneakyNumbers(int[] nums) {
        Arrays.sort(nums);
        List<Integer> duplicates = new ArrayList<>();
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i+1]) {
                duplicates.add(nums[i]);
            }
        }
        
        int[] result = new int[duplicates.size()];
        for (int i = 0; i < duplicates.size(); i++) {
            result[i] = duplicates.get(i);
        }
        return result;
    }
}
```
### Algorithm
- First, sort the input array `nums` in ascending order.
- Initialize an empty list, `duplicates`, to store the found numbers.
- Iterate through the sorted array from `i = 0` to `nums.length - 2`.
- In each iteration, compare the current element `nums[i]` with the next element `nums[i+1]`.
- If `nums[i] == nums[i+1]`, a duplicate is found. Add `nums[i]` to the `duplicates` list.
- After the loop, convert the `duplicates` list to an array and return it.

## Using a Hash Set
A linear time complexity solution can be achieved using a hash set. We can iterate through the array once, using the hash set to keep track of the numbers we've already seen. A hash set provides average O(1) time for lookups and insertions.
**Time:** O(N), where N is the length of `nums`. We iterate through the array once, and each hash set operation takes O(1) time on average. · **Space:** O(n), where `n` is the number of unique elements (`n = nums.length - 2`). In the worst case, the `seen` set will store `n` elements before the duplicates are found.
**Pros:** Efficient with O(N) time complexity.; Simple and clean logic.
**Cons:** Requires extra space proportional to the number of unique elements, which can be O(n).
### Explanation
We traverse the input array `nums` from left to right. We use a `HashSet` to store the unique numbers we encounter. For each number, we check if it's already in our set. If it is, we've found a duplicate. If not, we add it to the set. This allows us to find both duplicates in a single pass.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public int[] findTwoSneakyNumbers(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        List<Integer> duplicates = new ArrayList<>();
        for (int num : nums) {
            if (!seen.add(num)) {
                duplicates.add(num);
            }
        }
        
        int[] result = new int[duplicates.size()];
        for (int i = 0; i < duplicates.size(); i++) {
            result[i] = duplicates.get(i);
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty `HashSet<Integer>` called `seen` to track numbers encountered.
- Initialize an empty `List<Integer>` called `duplicates` to store the result.
- Iterate through each number `num` in the `nums` array.
- For each `num`, attempt to add it to the `seen` set using `seen.add(num)`.
- The `add` method returns `false` if the element already exists in the set. If it returns `false`, we have found a duplicate. Add `num` to the `duplicates` list.
- After iterating through all numbers, convert the `duplicates` list to an array and return it.

## In-place Modification (Optimal)
The most optimal solution in terms of space complexity takes advantage of the problem's constraints: the numbers are non-negative and fall within a specific range `[0, n-1]`. This allows us to use the input array itself as a hash map to store frequency counts, achieving O(1) auxiliary space.
**Time:** O(N), where N is the length of `nums`. We perform a constant number of passes over the array. · **Space:** O(1) auxiliary space. We only use a list to store the final result, which has a constant size of 2. The counting is done in-place.
**Pros:** Extremely efficient, with O(N) time and O(1) space complexity.; No external data structures are needed.
**Cons:** This approach modifies the input array, which might not be allowed in some scenarios.; The logic is more complex and less intuitive than the hash set approach.
### Explanation
This clever technique avoids using any extra data structures by modifying the array elements in-place. Since all numbers are in the range `[0, n-1]`, we can use the array indices `0` to `n-1` to store information about the frequency of each number.

We make two passes. In the first pass, for each number `val` in the array, we add `n` to the element at `nums[val % n]`. The modulo is used to retrieve the original number if the value at `nums[i]` has already been incremented. After this pass, the value at `nums[i]` will be `original_value + k * n`, where `k` is the frequency of the number `i`.

In the second pass, we iterate from `i = 0` to `n-1`. We can find the frequency of each number `i` by calculating `nums[i] / n`. If the result is 2, then `i` is one of the sneaky numbers.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] findTwoSneakyNumbers(int[] nums) {
        List<Integer> duplicates = new ArrayList<>();
        int n = nums.length - 2;

        // First pass: Use array indices to count frequencies
        for (int i = 0; i < nums.length; i++) {
            int index = nums[i] % n;
            nums[index] += n;
        }

        // Second pass: Find the indices where the count is 2
        for (int i = 0; i < n; i++) {
            if ((nums[i] / n) == 2) {
                duplicates.add(i);
            }
        }

        // Note: The input array is modified. If required, a third pass
        // could restore it by taking `nums[i] = nums[i] % n`.

        int[] result = new int[duplicates.size()];
        for (int i = 0; i < duplicates.size(); i++) {
            result[i] = duplicates.get(i);
        }
        return result;
    }
}
```
### Algorithm
- Determine the value of `n`, which is `nums.length - 2`.
- Iterate through the `nums` array from `i = 0` to `nums.length - 1`.
- For each element `nums[i]`, calculate an index `index = nums[i] % n`. This gives the original value, in case the element has been modified.
- Add `n` to the element at this index: `nums[index] += n`. This uses the array slot corresponding to a value to count its occurrences.
- After the first pass, initialize an empty list `duplicates`.
- Iterate from `i = 0` to `n - 1`.
- For each index `i`, check if `nums[i] / n` is equal to 2. If it is, it means the number `i` appeared twice in the original array. Add `i` to the `duplicates` list.
- Convert the `duplicates` list to an array and return it.

# Solutions
### Java

```java
class Solution {
public
  int[] getSneakyNumbers(int[] nums) {
    int[] ans = new int[2];
    int[] cnt = new int[100];
    int k = 0;
    for (int x : nums) {
      if (++cnt[x] == 2) {
        ans[k++] = x;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> getSneakyNumbers(vector<int> &nums) {
    vector<int> ans;
    int cnt[100]{};
    for (int x : nums) {
      if (++cnt[x] == 2) {
        ans.push_back(x);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]: cnt = Counter(nums) return [x for x, v in cnt . items() if v == 2]

```