Unique Frequencies in Signal Sequence — Problem Statement & Solution Guide
Problem Description
You are given an integer array nums that represents a sequence of signal frequencies. A frequency is considered *unique* if it occurs exactly once in the entire array. Write a function that returns a new array containing all unique frequencies, preserving their original left‑to‑right order from nums. If no frequency is unique, return an empty array.
The function signature should be:
vector<int> uniqueFrequencies(vector<int>& nums);
The returned array must contain the unique values in the same order they first appear in nums.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Unique Frequencies in Signal Sequence"
WHY DOES IT MATTER?
Counting frequencies with a hash map is a fundamental pattern for deduplication, majority element detection, and histogram building, which appear in many interview problems and real‑world data pipelines.
OPTIMIZATION CHALLENGE
The key insight is to decouple counting from ordering: first gather frequencies in O(n) using constant‑time map updates, then perform a second pass that respects the original sequence, avoiding nested loops or expensive sorting.
REAL-WORLD CONNECTION
In distributed logging systems, each log entry's identifier may need to be flagged as unique to trigger alerts; a central aggregator uses a hash table to count occurrences and then emits only the identifiers seen once, mirroring this algorithm.
When coding under pressure, first write the frequency‑count loop, then immediately write the collection loop; this two‑step structure is easy to debug and guarantees order preservation without extra bookkeeping.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem reduces to identifying elements that appear exactly once in a list while preserving their original order. A naïve solution would compare each element with every other element, leading to O(n²) time, which quickly becomes infeasible for large inputs. The optimal paradigm leverages a hash map (or unordered_map) to count occurrences in a single linear pass, then iterates a second time to collect those with a count of one, achieving O(n) time and O(n) auxiliary space. This two‑phase approach separates counting from ordering, allowing us to maintain the left‑to‑right sequence without extra sorting or complex data structures.
Interview Questions on This Problem
Q1How would you modify the solution if the input array is read as a stream and you cannot store the entire array in memory?
Use a hash map to keep frequency counts while streaming, and maintain a secondary queue that holds candidates seen exactly once; when a duplicate is detected, remove it from the queue. At the end of the stream, the queue contains the unique elements in order, using O(k) space where k is the number of distinct values.
Q2Can you solve the problem in O(n) time without using extra space beyond O(1) besides the output array?
If the value range is bounded (e.g., frequencies are within a small integer range), you can use a fixed-size array as a frequency counter, achieving O(1) extra space; otherwise, O(n) auxiliary space is required to store arbitrary counts.
Q3What would be the impact on time and space complexity if the array is sorted before processing?
Sorting costs O(n log n) time and O(1) or O(n) space depending on the algorithm, after which a single linear scan can identify unique elements. This is slower than the hash‑map solution for unsorted data, but it eliminates the need for a hash map when in‑place sorting is acceptable.
Examples
Input
[4,2,5,2,3,4,1]
Output
[5,3,1]
Explanation: First count occurrences: 4→2 times, 2→2 times, 5→1 time, 3→1 time, 1→1 time. Scan the original array and keep only those with a count of 1. The elements that satisfy this are 5 (at index 2), 3 (at index 4), and 1 (at index 6). Hence the result is [5, 3, 1].
Input
[7,7,7,7]
Output
[]
Explanation: All elements are the same and appear four times, so no element has a frequency of exactly one. The function returns an empty array.
Input
[-3,0,-3,8,2,0,9]
Output
[8,2,9]
Explanation: Frequency table: -3→2, 0→2, 8→1, 2→1, 9→1. Traversing the input left to right, the values with a count of 1 are 8 (index 3), 2 (index 4), and 9 (index 6). The output preserves this order: [8, 2, 9].
Constraints
- 1 <= nums.length <= 100000
- -1000000000 <= nums[i] <= 1000000000
- The algorithm should run in O(n) time where n is the length of `nums`.
- Only O(n) additional auxiliary space is allowed (e.g., for a hash map).
Optimal Approach & Strategy
Use a hash map to count frequencies in one pass, then iterate once more to collect elements with a count of one, preserving the original order.
Brute Force Approach
For each element, scan the entire array to count its occurrences and collect it if the count is one; this requires two nested loops.
Verified Code Solutions
function uniqueFrequencies(nums) {
const freq = new Map();
for (const num of nums) {
freq.set(num, (freq.get(num) || 0) + 1);
}
const result = [];
for (const num of nums) {
if (freq.get(num) === 1) {
result.push(num);
}
}
return result;
}#include <vector>
#include <unordered_map>
using namespace std;
vector<int> uniqueFrequencies(const vector<int>& nums) {
unordered_map<int, int> freq;
for (int num : nums) {
++freq[num];
}
vector<int> result;
for (int num : nums) {
if (freq[num] == 1) {
result.push_back(num);
}
}
return result;
}
import java.util.*;
public class Solution {
public List<Integer> uniqueFrequencies(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
List<Integer> result = new ArrayList<>();
for (int num : nums) {
if (freq.get(num) == 1) {
result.add(num);
}
}
return result;
}
}
def unique_frequencies(nums):
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
result = [num for num in nums if freq[num] == 1]
return result
function uniqueFrequencies(nums) {
const freq = new Map();
for (const num of nums) {
freq.set(num, (freq.get(num) || 0) + 1);
}
const result = [];
for (const num of nums) {
if (freq.get(num) === 1) {
result.push(num);
}
}
return result;
}
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.