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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
The Two Sneaky Numbers of Digitville | Leetcode #3289 • Techdose • 1,105 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