The Two Sneaky Numbers of Digitville

easy array hash table counting

Problem

A list nums was meant to hold every integer from 0 to n − 1 exactly once, but two mischievous numbers each sneaked in one extra time, so nums.length == n + 2. Find those two repeated numbers and return them in an array of size two (in any order).

Inputnums = [0, 1, 1, 0]

Output[0, 1]

Here n = 2, so values 0 and 1 should each appear once — but both appear twice, so they are the two sneaky numbers.

nums (comma-separated, values 0..n−1, length n+2)

def getSneakyNumbers(nums):
    n = len(nums) - 2          # values range over 0 .. n-1
    count = [0] * n            # count[v] = times we've seen v
    res = []
    for v in nums:
        count[v] += 1          # tally this value
        if count[v] == 2:      # second sighting -> sneaky
            res.append(v)
    return res                 # exactly two numbers collected

function getSneakyNumbers(nums) {
  const n = nums.length - 2;        // values range over 0 .. n-1
  const count = new Array(n).fill(0); // count[v] = times seen
  const res = [];
  for (const v of nums) {
    count[v]++;                     // tally this value
    if (count[v] === 2) {           // second sighting -> sneaky
      res.push(v);
    }
  }
  return res;                       // exactly two numbers collected
}

int[] getSneakyNumbers(int[] nums) {
    int n = nums.length - 2;        // values range over 0 .. n-1
    int[] count = new int[n];       // count[v] = times seen
    int[] res = new int[2];
    int idx = 0;
    for (int v : nums) {
        count[v]++;                 // tally this value
        if (count[v] == 2) {        // second sighting -> sneaky
            res[idx++] = v;
        }
    }
    return res;                     // exactly two numbers collected
}

vector<int> getSneakyNumbers(vector<int>& nums) {
    int n = nums.size() - 2;        // values range over 0 .. n-1
    vector<int> count(n, 0);        // count[v] = times seen
    vector<int> res;
    for (int v : nums) {
        count[v]++;                 // tally this value
        if (count[v] == 2) {        // second sighting -> sneaky
            res.push_back(v);
        }
    }
    return res;                     // exactly two numbers collected
}

Explanation

This is a classic counting problem. Every value in nums lies in the range 0 .. n−1, and each is supposed to appear exactly once — except the two sneaky numbers, which appear twice. So all we need is the frequency of each value.

Because the values are small bounded integers, we can use an array count of length n as a direct-address hash map: count[v] stores how many times we have seen v. A general HashMap<value, count> works identically and is the natural tool when values are not nicely bounded.

We sweep through nums once. For each value v we increment count[v]. The instant a count reaches 2, we know v is one of the duplicates, so we record it. Since the input is guaranteed to contain exactly two repeated elements, this collects exactly two numbers and we return them.

Catching each duplicate at its second sighting (rather than scanning the counts afterwards) keeps the whole thing to a single pass and avoids reporting the same number more than once.

Example: nums = [0, 1, 1, 0]. We see 0 (count 1), 1 (count 1), 1 again (count 2 → sneaky), 0 again (count 2 → sneaky). Result: [1, 0], which is valid since order does not matter.

Time: O(n) Space: O(n)