The Two Sneaky Numbers of Digitville
EasyPrompt
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] < n- The input is generated such that
numscontains exactly two repeated elements.
Approaches
4 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize an empty
Setcalledduplicatesto store the results and avoid adding the same number twice. - Use a nested loop structure. The outer loop iterates from
i = 0tonums.length - 1. - The inner loop iterates from
j = i + 1tonums.length - 1. - Inside the inner loop, compare
nums[i]andnums[j]. - If
nums[i] == nums[j], it signifies a duplicate. Addnums[i]to theduplicatesset. - After the loops complete, convert the
duplicatesset into an array and return it.
Walkthrough
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 1s finds a duplicate, and comparing the first and third 1s finds the same duplicate. The set ensures we only store 1 once.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- First, sort the input array
numsin ascending order. - Initialize an empty list,
duplicates, to store the found numbers. - Iterate through the sorted array from
i = 0tonums.length - 2. - In each iteration, compare the current element
nums[i]with the next elementnums[i+1]. - If
nums[i] == nums[i+1], a duplicate is found. Addnums[i]to theduplicateslist. - After the loop, convert the
duplicateslist to an array and return it.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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).
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.
Algorithm
- Initialize an empty
HashSet<Integer>calledseento track numbers encountered. - Initialize an empty
List<Integer>calledduplicatesto store the result. - Iterate through each number
numin thenumsarray. - For each
num, attempt to add it to theseenset usingseen.add(num). - The
addmethod returnsfalseif the element already exists in the set. If it returnsfalse, we have found a duplicate. Addnumto theduplicateslist. - After iterating through all numbers, convert the
duplicateslist to an array and return it.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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).
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.
Algorithm
- Determine the value of
n, which isnums.length - 2. - Iterate through the
numsarray fromi = 0tonums.length - 1. - For each element
nums[i], calculate an indexindex = nums[i] % n. This gives the original value, in case the element has been modified. - Add
nto 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 = 0ton - 1. - For each index
i, check ifnums[i] / nis equal to 2. If it is, it means the numberiappeared twice in the original array. Addito theduplicateslist. - Convert the
duplicateslist to an array and return it.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};class Solution: def getSneakyNumbers(self, nums: List[int]) -> List[int]: cnt = Counter(nums) return [x for x, v in cnt . items() if v == 2]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.