Count Unique Identifiers — Problem Statement & Solution Guide
Problem Description
You are provided with an array of integers representing system-generated identifiers. Your task is to analyze the distribution of these values to determine two specific metrics: the count of distinct identifiers present in the array and the total number of elements that are duplicates (i.e., elements that appear more than once). Note that if an identifier appears $k$ times where $k > 1$, all $k$ occurrences are counted toward the duplicate total, not just the excess occurrences.
The input will be a single array of integers. The output must be a pair of integers: the first representing the number of unique values, and the second representing the total count of duplicate elements. This analysis is critical for data integrity checks where both the diversity of the dataset and the volume of redundant entries need to be quantified simultaneously.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Count Unique Identifiers"
WHY DOES IT MATTER?
Counting distinct elements and duplicates is a classic frequency‑analysis pattern that appears in data cleaning, log analysis, and fraud detection, where understanding repetition is crucial for downstream decisions.
OPTIMIZATION CHALLENGE
The key insight is to avoid nested loops by maintaining a single pass frequency map, turning a quadratic problem into linear time while keeping memory proportional only to the number of unique identifiers.
REAL-WORLD CONNECTION
In a distributed logging system, each log entry has a request ID; counting how many IDs appear more than once helps detect retries or duplicate processing, analogous to the problem's duplicate count.
During an interview, first state the hash‑map approach, then discuss edge cases (empty array, all duplicates) and optionally mention the sorting fallback if constant extra space is required.
COMPLEXITY AT A GLANCE
O(n)O(u) ⊆ O(n)Core Theory — Why This Approach?
The problem reduces to counting distinct elements and the total number of duplicate occurrences in a list of integers. A naive solution would scan the array for each element and count its frequency, leading to O(n²) time, which quickly becomes infeasible for large inputs (n up to 10⁵ or more). The optimal paradigm leverages a hash‑based frequency map (or a balanced BST) to record how many times each identifier appears in a single linear pass, allowing constant‑time updates and look‑ups per element. Once the frequencies are known, the number of unique identifiers is simply the size of the map, while the duplicate count is the sum of (freq‑1) for every entry where freq > 1.
Using a hash map (e.g., unordered_map in C++ or dict in Python) yields O(n) expected time because each insertion and lookup is amortized O(1). The space overhead is O(u), where u is the number of distinct identifiers, bounded by O(n) in the worst case. This approach also naturally handles negative numbers and large ranges without needing auxiliary arrays or sorting, making it robust for real‑world identifier spaces that may be sparse or non‑contiguous.
Interview Questions on This Problem
Q1How would you modify the solution if the identifiers could be up to 10⁹ and you are constrained to O(1) extra space?
You would sort the array in‑place (O(n log n) time) and then scan once, counting unique values and duplicates by comparing adjacent elements. Sorting eliminates the need for extra storage beyond the input array.
Q2Explain how you could compute the same metrics in a distributed setting where the array is partitioned across multiple machines.
Each node builds a local frequency map for its partition, then a reduce step merges the maps by summing frequencies for each identifier. The final unique count is the number of keys with total frequency > 0, and duplicate count is the sum of (totalFreq‑1) for keys where totalFreq > 1.
Q3If the input stream is infinite (e.g., a live feed of identifiers), how can you approximate the number of distinct identifiers using limited memory?
Use probabilistic algorithms like HyperLogLog or Linear Counting, which maintain a compact sketch of the stream and can estimate cardinality with bounded error while using sub‑linear space.
Examples
Input
ids = [10, 20, 10, 30, 20, 40]
Output
[4, 4]
Explanation: The distinct values are {10, 20, 30, 40}, so the unique count is 4. The value 10 appears twice and 20 appears twice. The total number of duplicate elements is 2 (from 10) + 2 (from 20) = 4. Thus, the output is [4, 4].
Input
ids = [5, 5, 5, 5]
Output
[1, 4]
Explanation: The only distinct value is {5}, so the unique count is 1. The value 5 appears four times. Since all occurrences are part of a duplicate group, the total duplicate count is 4. Thus, the output is [1, 4].
Input
ids = [1, 2, 3, 4, 5]
Output
[5, 0]
Explanation: All values {1, 2, 3, 4, 5} are distinct, so the unique count is 5. No value appears more than once, so the duplicate count is 0. Thus, the output is [5, 0].
Input
ids = [100, 200, 100, 300, 100, 200]
Output
[3, 5]
Explanation: The distinct values are {100, 200, 300}, so the unique count is 3. The value 100 appears three times and 200 appears twice. The total duplicate count is 3 (from 100) + 2 (from 200) = 5. Thus, the output is [3, 5].
Constraints
- 1 <= ids.length <= 10^5
- -10^9 <= ids[i] <= 10^9
- The array may contain negative integers and zero.
Optimal Approach & Strategy
Use a hash map to record frequencies in a single traversal; then derive distinct and duplicate counts from the map.
Brute Force Approach
Iterate over each element and, for each, scan the entire array to count its occurrences, updating counters accordingly.
Verified Code Solutions
/**
* @param {number[]} ids
* @return {number[]}
*/
var countUniqueIdentifiers = function(ids) {
const freq = new Map();
for (const id of ids) {
freq.set(id, (freq.get(id) || 0) + 1);
}
const uniqueCount = freq.size;
let duplicateCount = 0;
for (const count of freq.values()) {
if (count > 1) {
duplicateCount += count;
}
}
return [uniqueCount, duplicateCount];
};class Solution {
public:
vector<int> countUniqueIdentifiers(vector<int>& ids) {
unordered_map<int, int> freq;
for (int id : ids) {
freq[id]++;
}
int uniqueCount = freq.size();
int duplicateCount = 0;
for (auto& p : freq) {
if (p.second > 1) {
duplicateCount += p.second;
}
}
return {uniqueCount, duplicateCount};
}
};class Solution {
public int[] countUniqueIdentifiers(int[] ids) {
Map<Integer, Integer> freq = new HashMap<>();
for (int id : ids) {
freq.put(id, freq.getOrDefault(id, 0) + 1);
}
int uniqueCount = freq.size();
int duplicateCount = 0;
for (int count : freq.values()) {
if (count > 1) {
duplicateCount += count;
}
}
return new int[]{uniqueCount, duplicateCount};
}
}class Solution:
def countUniqueIdentifiers(self, ids: List[int]) -> List[int]:
freq = {}
for id in ids:
freq[id] = freq.get(id, 0) + 1
unique_count = len(freq)
duplicate_count = sum(count for count in freq.values() if count > 1)
return [unique_count, duplicate_count]/**
* @param {number[]} ids
* @return {number[]}
*/
var countUniqueIdentifiers = function(ids) {
const freq = new Map();
for (const id of ids) {
freq.set(id, (freq.get(id) || 0) + 1);
}
const uniqueCount = freq.size;
let duplicateCount = 0;
for (const count of freq.values()) {
if (count > 1) {
duplicateCount += count;
}
}
return [uniqueCount, duplicateCount];
};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.