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 <= 100nums.length == n + 20 <= nums[i] < nnums contains exactly two repeated elements.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.
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.
This C solution uses an array called frequency to track how many times each number appears. It initializes the array to the size of n, where n is the upper range of numbers. As the array is traversed, we increment the count for each number in the frequency array. Lastly, we loop through the frequency array to find numbers with counts greater than one. These numbers are the repeated 'sneaky' numbers.
Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(n), to store the frequency of each number.
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.
This C solution involves sorting the array using qsort. A single pass through the sorted array is undertaken to find matching consecutive numbers, appending these 'sneaky' numbers to the result array.
Time Complexity: O(n log n), driven by the sorting operation.
Space Complexity: O(1), if we do not count the space required for sorting.
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.
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:
1 in the binary representation of xx, denoted as k. This position indicates that the two numbers differ at this bit.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).
| Approach | Complexity |
|---|---|
| Approach Using a Frequency Dictionary | Time Complexity: O(n), where n is the number of elements in |
| Approach Using Sorting and Pairwise Comparison | Time Complexity: O(n log n), driven by the sorting operation. |
| Counting | — |
| Bit Manipulation | — |
| 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 |
The Two Sneaky Numbers of Digitville | Learn Important Bit Concept | Dry Runs | Leetcode 3289 | MIK • codestorywithMIK • 4,352 views views
Watch 9 more video solutions →Practice The Two Sneaky Numbers of Digitville with our built-in code editor and test cases.
Practice on FleetCode