3289. The Two Sneaky Numbers of Digitville Solution

Q: Is The Two Sneaky Numbers of Digitville easy or hard?

The problem is classified as Easy. It mainly tests basic array traversal and duplicate detection using a hash table. Candidates familiar with frequency counting patterns can usually solve it quickly in O(n) time.

Q: The Two Sneaky Numbers of Digitville Python/Java solution

In Python, a dictionary or collections.Counter can track frequencies while iterating through the array. In Java, a HashMap performs the same role. Both implementations scan the array once and record values that appear twice.

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

Approach overview

Problem Overview: You receive an integer array that contains numbers from 0 to n-1, but two numbers appear twice. Every other number appears exactly once. The task is to identify those two duplicated values (the “sneaky numbers”) and return them.

Approach 1: Frequency Dictionary (Hash Table) (Time: O(n), Space: O(n))

The most direct solution uses a frequency counter. Iterate through the array and store counts in a hash table (dictionary). Each time you encounter a number, increment its frequency. When a value reaches a count of 2, it is one of the sneaky numbers. Continue scanning until both duplicates are found. Hash tables provide average O(1) insert and lookup operations, so the entire array can be processed in linear time.

This approach works well for unsorted arrays and is typically the first solution engineers reach for when detecting duplicates. It trades additional memory for simplicity and speed. The technique relies on efficient key lookups from a hash table while iterating once through the array. If interview constraints allow extra space, this is the cleanest implementation.

Approach 2: Sorting and Pairwise Comparison (Time: O(n log n), Space: O(1) or O(log n))

A second approach avoids explicit extra storage by sorting the array first. Once sorted, duplicate values will appear next to each other. After sorting, iterate through the array and compare each element with the next one. Whenever nums[i] == nums[i+1], that value is one of the sneaky numbers.

The key insight is that sorting groups identical values together, turning duplicate detection into a simple adjacency check. The main cost comes from the sorting step, which takes O(n log n) time. Depending on the language and sorting implementation, space usage ranges from constant to O(log n). This approach is useful when memory is constrained or when the array is already nearly sorted.

Recommended for interviews: The hash table solution is usually the expected answer because it achieves optimal O(n) time with straightforward logic. Interviewers often accept the sorting approach as a valid alternative, especially if you discuss the tradeoff between extra memory and sorting overhead. Demonstrating both shows strong understanding of hash table lookup patterns and fundamental counting strategies used for duplicate detection.

Approach 1: Approach Using a Frequency Dictionary

This approach involves using a dictionary or hash map to keep track of the frequency of each number in the array. You can iterate through the list and update the map with the count of each number. After building the frequency map, identify the numbers that have a frequency greater than one; these would be the sneaky numbers that appear an additional time.

Python

def find_sneaky_numbers(nums):
    frequency = {}
    result = []
    
    for num in nums:
        if num in frequency:
            frequency[num] += 1
        else:
            frequency[num] = 1
    
    for num, count in frequency.items():
        if count > 1:
            result.append(num)
    return result

nums = [0, 3, 2, 1, 3, 2]
result = find_sneaky_numbers(nums)
print(result)

Java

import java.util.HashMap;
import java.util.Map;
import java.util.List;
import java.util.ArrayList;

public class Main {
    public static List<Integer> findSneakyNumbers(int[] nums) {
        Map<Integer, Integer> frequency = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        
        for (int num : nums) {
            frequency.put(num, frequency.getOrDefault(num, 0) + 1);
        }
        
        for (Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
            if (entry.getValue() > 1) {
                result.add(entry.getKey());
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[] nums = {0, 3, 2, 1, 3, 2};
        List<Integer> result = findSneakyNumbers(nums);
        System.out.println(result);
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> findSneakyNumbers(vector<int>& nums) {
    unordered_map<int, int> frequency;
    vector<int> result;
    
    for (int num : nums) {
        frequency[num]++;
    }
    
    for (const auto& pair : frequency) {
        if (pair.second > 1) {
            result.push_back(pair.first);
        }
    }
    return result;
}

int main() {
    vector<int> nums = {0, 3, 2, 1, 3, 2};
    vector<int> result = findSneakyNumbers(nums);
    cout << "[" << result[0] << ", " << result[1] << "]" << endl;
    return 0;
}

JavaScript

function findSneakyNumbers(nums) {
    const frequency = {};
    const result = [];
    
    nums.forEach(num => {
        if (frequency[num] !== undefined) {
            frequency[num]++;
        } else {
            frequency[num] = 1;
        }
    });
    
    for (const num in frequency) {
        if (frequency[num] > 1) {
            result.push(parseInt(num));
        }
    }
    return result;
}

const nums = [0, 3, 2, 1, 3, 2];
const result = findSneakyNumbers(nums);
console.log(result);

#include <stdio.h>
#include <stdlib.h>

int* findSneakyNumbers(int* nums, int numsSize, int* returnSize) {
    int* frequency = (int*)calloc(numsSize - 2, sizeof(int));
    int* result = (int*)malloc(2 * sizeof(int));
    *returnSize = 0;
    
    for (int i = 0; i < numsSize; i++) {
        frequency[nums[i]]++;
    }
    
    for (int i = 0; i < numsSize - 2; i++) {
        if (frequency[i] > 1) {
            result[(*returnSize)++] = i;
        }
    }
    free(frequency);
    return result;
}

int main() {
    int nums[] = {0, 3, 2, 1, 3, 2};
    int returnSize;
    int* result = findSneakyNumbers(nums, 6, &returnSize);
    printf("[%d, %d]\n", result[0], result[1]);
    free(result);
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public static List<int> FindSneakyNumbers(int[] nums) {
        Dictionary<int, int> frequency = new Dictionary<int, int>();
        List<int> result = new List<int>();

        foreach (int num in nums) {
            if (frequency.ContainsKey(num)) {
                frequency[num]++;
            } else {
                frequency[num] = 1;
            }
        }

        foreach (var entry in frequency) {
            if (entry.Value > 1) {
                result.Add(entry.Key);
            }
        }
        return result;
    }

    public static void Main(string[] args) {
        int[] nums = {0, 3, 2, 1, 3, 2};
        List<int> result = FindSneakyNumbers(nums);
        Console.WriteLine("[" + string.Join(", ", result) + "]");
    }
}

Here, we use a Python dictionary to count occurrences of each number. Loop through the input nums list, updating the dictionary's count for each number. Finally, identify those numbers whose count exceeds one and return them.

Complexity

Time Complexity: O(n), as adding elements to or querying the dictionary can be done in constant time on average.
Space Complexity: O(n), considering the space utilized by the frequency dictionary.

Try this approach in the editor

Approach 2: Approach Using Sorting and Pairwise Comparison

Another method is to first sort the array. Once sorted, any repeated numbers will appear consecutively. Thus, a linear scan of the sorted array identifies sneaky numbers by checking each pair of consecutive elements.

Python

def find_sneaky_numbers(nums):
    nums.sort()
    result = []

    i = 1
    while i < len(nums):
        if nums[i] == nums[i - 1]:
            result.append(nums[i])
            i += 1  # Skip the next duplicate
        i += 1
    return result

nums = [0, 3, 2, 1, 3, 2]
result = find_sneaky_numbers(nums)
print(result)

Java

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

public class Main {
    public static List<Integer> findSneakyNumbers(int[] nums) {
        Arrays.sort(nums);
        List<Integer> result = new ArrayList<>();

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                result.add(nums[i]);
                i++;  // Skip the next duplicate
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {0, 3, 2, 1, 3, 2};
        List<Integer> result = findSneakyNumbers(nums);
        System.out.println(result);
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> findSneakyNumbers(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> result;

    for (size_t i = 1; i < nums.size(); ++i) {
        if (nums[i] == nums[i - 1]) {
            result.push_back(nums[i]);
            i++;  // Skip the next duplicate
        }
    }
    return result;
}

int main() {
    vector<int> nums = {0, 3, 2, 1, 3, 2};
    vector<int> result = findSneakyNumbers(nums);
    cout << "[" << result[0] << ", " << result[1] << "]" << endl;
    return 0;
}

JavaScript

function findSneakyNumbers(nums) {
    nums.sort((a, b) => a - b);
    const result = [];

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) {
            result.push(nums[i]);
            i++;  // Skip the next duplicate
        }
    }
    return result;
}

const nums = [0, 3, 2, 1, 3, 2];
const result = findSneakyNumbers(nums);
console.log(result);

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int* findSneakyNumbers(int* nums, int numsSize, int* returnSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    int* result = (int*)malloc(2 * sizeof(int));
    *returnSize = 0;

    for (int i = 1; i < numsSize; i++) {
        if (nums[i] == nums[i - 1]) {
            result[(*returnSize)++] = nums[i];
            i++;  // skip the next duplicate
        }
    }
    return result;
}

int main() {
    int nums[] = {0, 3, 2, 1, 3, 2};
    int returnSize;
    int* result = findSneakyNumbers(nums, 6, &returnSize);
    printf("[%d, %d]\n", result[0], result[1]);
    free(result);
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public static List<int> FindSneakyNumbers(int[] nums) {
        Array.Sort(nums);
        List<int> result = new List<int>();

        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] == nums[i - 1]) {
                result.Add(nums[i]);
                i++;  // Skip the next duplicate
            }
        }
        return result;
    }

    public static void Main(string[] args) {
        int[] nums = {0, 3, 2, 1, 3, 2};
        List<int> result = FindSneakyNumbers(nums);
        Console.WriteLine("[" + string.Join(", ", result) + "]");
    }
}

This Python solution sorts the list first, then compares adjacent elements to find duplicates. These are appended to the result list.

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) additional space beyond inputs.

Try this approach in the editor

Approach 3: Counting

We can use an array cnt to record the number of occurrences of each number.

Traverse the array nums, and when a number appears for the second time, add it to the answer array.

After the traversal, return the answer array.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

TypeScript

function getSneakyNumbers(nums: number[]): number[] {
    const ans: number[] = [];
    const cnt: number[] = Array(100).fill(0);
    for (const x of nums) {
        if (++cnt[x] > 1) {
            ans.push(x);
        }
    }
    return ans;
}

func getSneakyNumbers(nums []int) (ans []int) {
	cnt := [100]int{}
	for _, x := range nums {
		cnt[x]++
		if cnt[x] == 2 {
			ans = append(ans, x)
		}
	}
	return
}

Rust

use std::collections::HashMap;

impl Solution {
    pub fn get_sneaky_numbers(nums: Vec<i32>) -> Vec<i32> {
        let mut cnt = HashMap::new();
        for x in nums {
            *cnt.entry(x).or_insert(0) += 1;
        }
        let mut ans = Vec::new();
        for (x, v) in cnt {
            if v == 2 {
                ans.push(x);
            }
        }
        ans
    }
}

Try this approach in the editor

Approach 4: Bit Manipulation

Let the length of array nums be n + 2, which contains integers from 0 to n - 1, with two numbers appearing twice.

We can find these two numbers using XOR operations. First, we perform XOR operations on all numbers in array nums and the integers from 0 to n - 1. The result is the XOR value of the two duplicate numbers, denoted as xx.

Next, we can find certain characteristics of these two numbers through xx and separate them. The specific steps are as follows:

Find the position of the lowest bit or highest bit with value 1 in the binary representation of xx, denoted as k. This position indicates that the two numbers differ at this bit.
Based on the value of the k-th bit, divide the numbers in array nums and the integers from 0 to n - 1 into two groups: one group with 0 at the k-th bit, and another group with 1 at the k-th bit. Then perform XOR operations on these two groups separately, and the results are the two duplicate numbers.

The time complexity is O(n), where n is the length of array nums. The space complexity is O(1).

TypeScript

function getSneakyNumbers(nums: number[]): number[] {
    const n = nums.length - 2;
    let xx = nums[n] ^ nums[n + 1];
    for (let i = 0; i < n; ++i) {
        xx ^= i ^ nums[i];
    }
    const k = Math.clz32(xx & -xx) ^ 31;
    const ans = [0, 0];
    for (const x of nums) {
        ans[(x >> k) & 1] ^= x;
    }
    for (let i = 0; i < n; ++i) {
        ans[(i >> k) & 1] ^= i;
    }
    return ans;
}

func getSneakyNumbers(nums []int) []int {
	n := len(nums) - 2
	xx := nums[n] ^ nums[n+1]
	for i := 0; i < n; i++ {
		xx ^= i ^ nums[i]
	}
	k := bits.TrailingZeros(uint(xx))
	ans := make([]int, 2)
	for _, x := range nums {
		ans[(x>>k)&1] ^= x
	}
	for i := 0; i < n; i++ {
		ans[(i>>k)&1] ^= i
	}
	return ans
}

Rust

impl Solution {
    pub fn get_sneaky_numbers(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len() as i32 - 2;
        let mut xx = nums[n as usize] ^ nums[(n + 1) as usize];
        for i in 0..n {
            xx ^= i ^ nums[i as usize];
        }
        let k = xx.trailing_zeros();
        let mut ans = vec![0, 0];
        for &x in &nums {
            ans[((x >> k) & 1) as usize] ^= x;
        }
        for i in 0..n {
            ans[((i >> k) & 1) as usize] ^= i;
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach Using a Frequency Dictionary	Time Complexity: O(n), as adding elements to or querying the dictionary can be done in constant time on average. Space Complexity: O(n), considering the space utilized by the frequency dictionary.
Approach Using Sorting and Pairwise Comparison	Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) additional space beyond inputs.
Counting	–
Bit Manipulation	–

Complexity analysis

Approach	Time	Space	When to Use
Frequency Dictionary (Hash Table)	O(n)	O(n)	Best general solution for unsorted arrays when extra memory is allowed
Sorting + Pairwise Comparison	O(n log n)	O(1) to O(log n)	Useful when minimizing extra space or when the array can be sorted

Frequently asked questions

Is The Two Sneaky Numbers of Digitville easy or hard?

The problem is classified as Easy. It mainly tests basic array traversal and duplicate detection using a hash table. Candidates familiar with frequency counting patterns can usually solve it quickly in O(n) time.

The Two Sneaky Numbers of Digitville Python/Java solution

In Python, a dictionary or collections.Counter can track frequencies while iterating through the array. In Java, a HashMap<Integer, Integer> performs the same role. Both implementations scan the array once and record values that appear twice.

How to solve The Two Sneaky Numbers of Digitville in O(n)?

Use a frequency dictionary. Iterate through the array and track how many times each value appears. Whenever the count becomes two, add that number to the result list. Because the array is scanned only once and hash lookups are constant time, the total complexity is O(n).

What is the best approach for The Two Sneaky Numbers of Digitville?

The hash table frequency approach is the most efficient and commonly expected solution. Scan the array once while storing counts in a dictionary. When a value reaches frequency two, record it as a sneaky number. This method runs in O(n) time with O(n) extra space.

Is The Two Sneaky Numbers of Digitville asked at Google/Amazon/Meta?

Problems involving duplicate detection and frequency counting are common in interviews at companies like Amazon, Google, and Meta. While the exact problem title may vary, the pattern of identifying repeated numbers in an array using hashing appears frequently in coding rounds.

What data structure is used in The Two Sneaky Numbers of Digitville?

The primary data structure used in the optimal solution is a hash table (dictionary). It stores each number as a key and tracks how many times it appears. Sorting-based solutions instead rely on array ordering and adjacent comparisons.

What is the time complexity of The Two Sneaky Numbers of Digitville?

The optimal hash table solution runs in O(n) time because each element is processed once and dictionary lookups are O(1) on average. A sorting-based approach takes O(n log n) time due to the sorting step followed by a linear scan.

The Two Sneaky Numbers of Digitville solution and explanation

The problem

Approach overview

Approach 1: Approach Using a Frequency Dictionary

Approach 2: Approach Using Sorting and Pairwise Comparison

Approach 3: Counting

Approach 4: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

The Two Sneaky Numbers of Digitville solution and explanation

The problem

Approach overview

Approach 1: Approach Using a Frequency Dictionary

Approach 2: Approach Using Sorting and Pairwise Comparison

Approach 3: Counting

Approach 4: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems