LeetCode 3289 - The Two Sneaky Numbers of Digitville

LeetCode Problem 3289

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Math

Solution

Problem Understanding

The problem is asking us to identify two numbers that appear twice in an otherwise consecutive list of integers ranging from 0 to n - 1. In other words, the input nums is almost a permutation of the numbers 0 through n - 1, except that two numbers are repeated, so the length of nums is n + 2.

The input is a list of integers. Each integer is guaranteed to be in the range [0, n - 1]. The output is an array of size two, containing the repeated numbers in any order. The constraints guarantee exactly two duplicates, so we do not need to handle inputs with zero, one, or more than two duplicates.

Important edge cases to consider include: the repeated numbers being consecutive, repeated numbers being at the start or end of the list, and repeated numbers being equal to the maximum (n - 1) or minimum (0) values.

Given that n is up to 100, performance is not a major concern, but we should still aim for an efficient solution that scales linearly and avoids unnecessary extra space if possible.

Approaches

Brute Force

The simplest approach is to use nested loops to check each number against every other number. For each number in the list, count how many times it occurs. If it occurs more than once, it is a repeated number. This approach is guaranteed to find the duplicates but is O(n²) in time, which is unnecessarily slow, even for small n.

Optimal Approach

A better approach uses a hash table (dictionary in Python, map in Go) to keep track of counts. As we iterate over the list, we increment the count of each number in the hash table. When the count reaches two, we know the number is repeated and we add it to the output. This guarantees O(n) time and O(n) space.

The key insight is that since each number is in a small range [0, n - 1] and there are exactly two duplicates, we can safely track occurrences with a simple hash map. There is no need for sorting or more complex techniques.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Check every pair to count duplicates
Hash Map	O(n)	O(n)	Track counts as we iterate; add numbers to result when count reaches 2

Algorithm Walkthrough

1. Initialize an empty hash table (dictionary or map) to store counts of numbers.
2. Initialize an empty list res to store the two repeated numbers.
3. Iterate over each number in nums.
4. For each number, increment its count in the hash table.
5. If the count reaches 2, append the number to res because it is one of the duplicates.
6. Continue until the end of the list; the list res will contain exactly two numbers.
7. Return res.

Why it works: The algorithm works because we know exactly two numbers are repeated. By incrementing the count and checking when it reaches two, we capture each duplicate exactly once. The hash table ensures we can check counts in constant time.

Python Solution

from typing import List

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        counts = {}
        res = []
        for num in nums:
            counts[num] = counts.get(num, 0) + 1
            if counts[num] == 2:
                res.append(num)
        return res

The implementation initializes a dictionary counts to store how many times each number appears. For every number in nums, we increment its count. When a number appears for the second time, we append it to the result list res. Finally, we return the two sneaky numbers.

Go Solution

func getSneakyNumbers(nums []int) []int {
    counts := make(map[int]int)
    res := []int{}
    
    for _, num := range nums {
        counts[num]++
        if counts[num] == 2 {
            res = append(res, num)
        }
    }
    
    return res
}

The Go solution is almost identical to Python. We use a map to track counts and append numbers to a slice res when their count reaches 2. Go handles empty slices differently, but the logic is the same and safe because the slice grows dynamically.

Worked Examples

Example 1

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

Iteration	num	counts	res
1	0	{0:1}	[]
2	1	{0:1,1:1}	[]
3	1	{0:1,1:2}	[1]
4	0	{0:2,1:2}	[1,0]

Output: [1,0] (order does not matter)

Example 2

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

Iteration	num	counts	res
1-3	0,3,2	{0:1,3:1,2:1}	[]
4	1	{0:1,3:1,2:1,1:1}	[]
5	3	{0:1,3:2,2:1,1:1}	[3]
6	2	{0:1,3:2,2:2,1:1}	[3,2]

Output: [3,2]

Example 3

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

Duplicates found in order: 4,5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array, counting occurrences
Space	O(n)	Hash map stores counts of up to n distinct numbers

The algorithm is linear in both time and space. Since n ≤ 100, this is very efficient.

Test Cases

# Provided examples
assert Solution().getSneakyNumbers([0,1,1,0]) == [1,0] or Solution().getSneakyNumbers([0,1,1,0]) == [0,1]
assert Solution().getSneakyNumbers([0,3,2,1,3,2]) == [3,2] or Solution().getSneakyNumbers([0,3,2,1,3,2]) == [2,3]
assert Solution().getSneakyNumbers([7,1,5,4,3,4,6,0,9,5,8,2]) == [4,5] or Solution().getSneakyNumbers([7,1,5,4,3,4,6,0,9,5,8,2]) == [5,4]

# Edge cases
assert Solution().getSneakyNumbers([0,0,1,2]) == [0]  # Only 0 repeated at start
assert Solution().getSneakyNumbers([0,1,2,2,3]) == [2]  # Only 2 repeated in middle
assert Solution().getSneakyNumbers([0,1,2,3,3]) == [3]  # Only 3 repeated at end
assert Solution().getSneakyNumbers([0,1,2,3,4,4,2,5]) == [4,2] or Solution().getSneakyNumbers([0,1,2,3,4,4,2,5]) == [2,4]  # Repeats out of order

Test	Why
[0,1,1,0]	Simple two duplicates at beginning
[0,3,2,1,3,2]	Duplicates not adjacent, arbitrary order
[7,1,5,4,3,4,6,0,9,5,8,2]	Random order with larger numbers
[0,0,1,2]	Repeated at start of array
[0,1,2,2,3]	Repeated in the middle
[0,1,2,3,3]	Repeated at end
[0,1,2,3,4,4,2,5]	Repeats out of order

Edge Cases

The first important edge case is when both repeated numbers are 0 and 1. This could trip up implementations that assume duplicates are larger numbers. Our hash map counts occurrences of all numbers equally, so this works fine.

The second edge case is when both repeated numbers are the largest in the range, n - 2 and n - 1. Any index-based method could fail if it does not handle the upper bound correctly. Using a hash map handles all values in the valid range.

The third edge case is when