NEW OR EXISTING ID 2 — Problem Statement & Solution Guide
Problem Description
You are given an array of integers named nums. Your task is to identify every integer that appears in nums more than once and return a list containing each such integer exactly once. The resulting list must be sorted in ascending order. If no integer repeats, return an empty list. The input array can contain negative numbers, zero, and positive numbers, and its length can be up to 100,000 elements.
DSA Pattern Breakdown
DSA Pattern Breakdown
"NEW OR EXISTING ID 2"
WHY DOES IT MATTER?
Frequency counting is a core pattern for problems involving duplicates, anagrams, and element existence checks. Mastering this pattern allows you to solve a wide range of array and string problems efficiently by trading space for time.
OPTIMIZATION CHALLENGE
The key insight is using a hash map to count occurrences in O(1) average time per element, reducing the overall time complexity from O(n^2) to O(n). The subsequent sorting of the result list is O(k log k) where k is the number of unique duplicates, which is typically much smaller than n.
REAL-WORLD CONNECTION
This is analogous to detecting duplicate transactions in a financial ledger or identifying repeated IP addresses in network logs. In both cases, you need to quickly identify items that have occurred more than once to trigger alerts or deduplication logic.
Always clarify the constraints. If the range of integers is small (e.g., -100 to 100), you can use a fixed-size array for counting instead of a hash map, which is faster due to better cache locality. If the range is large, a hash map is the standard choice.
COMPLEXITY AT A GLANCE
O(n + k log k)O(n)Core Theory — Why This Approach?
The problem of identifying duplicate elements in an array is a fundamental application of frequency counting. The naive approach involves iterating through the array for each element to check if it appears elsewhere, resulting in a time complexity of O(n^2). For an array size of 100,000, this results in 10^10 operations, which is computationally infeasible for real-time systems or strict time limits. This quadratic behavior fails because it does not leverage the properties of hash-based data structures to achieve constant-time lookups.
Interview Questions on This Problem
Q1How would you modify this solution to handle a stream of data where the entire array is not available in memory at once?
You would use a hash map to maintain the count of each number as it arrives in the stream. Since the problem requires returning duplicates only once, you can maintain a set of 'seen' numbers and a set of 'duplicates'. When a number is encountered, if it is in 'seen', add it to 'duplicates'. Finally, sort the 'duplicates' set. This maintains O(1) average time per element and O(k) space where k is the number of unique elements.
Q2If the input array is guaranteed to be sorted, how does the optimal approach change, and what is the new time complexity?
If the array is sorted, you can use a single linear scan with O(1) extra space. You simply compare each element with the next one. If they are equal, you have found a duplicate. You must ensure you add each duplicate value only once to the result list (e.g., by checking if the current duplicate is the same as the last one added). The time complexity remains O(n) for the scan, but the sorting step is eliminated if the input is already sorted, or O(n log n) if sorting is required as part of the solution.
Q3In a distributed system, how would you detect duplicates across multiple nodes without centralizing all data?
You could use a distributed hash table or a bloom filter to track seen elements. Each node checks its local bloom filter; if an element is likely present, it performs a more expensive verification. Alternatively, you can use a consensus algorithm to agree on the set of duplicates. The key is to minimize network overhead by only communicating potential duplicates rather than the entire dataset.
Examples
Input
[1, 2, 3, 2, 4, 5, 1]
Output
[1, 2]
Explanation: Count occurrences: 1 appears twice, 2 appears twice, 3, 4, and 5 appear once. The duplicates are 1 and 2. Sorted ascending gives [1, 2].
Input
[10, 20, 30, 40]
Output
[]
Explanation: Each element appears only once, so there are no duplicates. The output is an empty list.
Input
[7, 7, 7, 7]
Output
[7]
Explanation: The number 7 appears four times. It is the only value that repeats, so the output list contains just 7.
Input
[-5, 0, -5, 10, 0, 10, 10]
Output
[-5, 0, 10]
Explanation: Occurrences: -5 appears twice, 0 appears twice, 10 appears three times. All three values are duplicates. Sorted ascending yields [-5, 0, 10].
Constraints
- 1 <= nums.length <= 100000
- -1000000000 <= nums[i] <= 1000000000
- The output list must contain each duplicate value exactly once and be sorted in ascending order.
Optimal Approach & Strategy
Use a hash map to count the frequency of each element in a single pass, then filter for elements with a count greater than 1 and sort the result. This achieves O(n) time for counting and O(k log k) for sorting the duplicates.
Brute Force Approach
Iterate through the array with two nested loops, comparing each element with every other element to check for duplicates. This results in a time complexity of O(n^2), which is too slow for large inputs.
Verified Code Solutions
/**
* @param {number[]} nums
* @return {number[]}
*/
var findDuplicates = function(nums) {
const seen = new Set();
const duplicates = new Set();
for (const num of nums) {
if (seen.has(num)) {
duplicates.add(num);
} else {
seen.add(num);
}
}
return Array.from(duplicates).sort((a, b) => a - b);
};class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
unordered_set<int> seen;
unordered_set<int> duplicates;
for (int num : nums) {
if (seen.count(num)) {
duplicates.insert(num);
} else {
seen.insert(num);
}
}
vector<int> result(duplicates.begin(), duplicates.end());
sort(result.begin(), result.end());
return result;
}
};class Solution {
public List<Integer> findDuplicates(int[] nums) {
Set<Integer> seen = new HashSet<>();
Set<Integer> duplicates = new HashSet<>();
for (int num : nums) {
if (seen.contains(num)) {
duplicates.add(num);
} else {
seen.add(num);
}
}
List<Integer> result = new ArrayList<>(duplicates);
Collections.sort(result);
return result;
}
}class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
seen = set()
duplicates = set()
for num in nums:
if num in seen:
duplicates.add(num)
else:
seen.add(num)
return sorted(duplicates)/**
* @param {number[]} nums
* @return {number[]}
*/
var findDuplicates = function(nums) {
const seen = new Set();
const duplicates = new Set();
for (const num of nums) {
if (seen.has(num)) {
duplicates.add(num);
} else {
seen.add(num);
}
}
return Array.from(duplicates).sort((a, b) => a - b);
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.