Sonar Signal Processor — Problem Statement & Solution Guide
Problem Description
A deep-sea monitoring station records a continuous stream of acoustic waveforms, represented as an array of integers where each integer denotes a specific signal frequency. The station's processing unit must filter this stream to identify the distinct signal types. Your task is to process the input array and return a list containing the first occurrence of each unique signal value, preserving the order in which they first appeared in the original sequence.
The input is a single array of integers. The output should be a new array containing only the unique values from the input, ordered by their first appearance. If a signal value repeats, it must be ignored in the output after its initial inclusion. This operation effectively removes duplicates while maintaining the relative order of the first occurrences.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Sonar Signal Processor"
WHY DOES IT MATTER?
Preserving order while deduplicating is a frequent requirement in data pipelines, log processing, and UI rendering, where the first occurrence carries semantic importance.
OPTIMIZATION CHALLENGE
The key insight is to replace repeated linear scans with a constant‑time membership test using a hash set, turning an O(n²) problem into O(n).
REAL-WORLD CONNECTION
Think of a network packet inspector that must forward only the first packet of each unique flow to a monitoring service, while discarding duplicates to reduce bandwidth usage.
During an interview, write the hash‑set solution first, then discuss edge cases (e.g., empty input, all duplicates) and possible memory‑friendly variations before coding.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The task of extracting the first occurrence of each distinct element while preserving the original order is a classic example of the "first‑unique‑preserve‑order" problem. A naive solution would repeatedly scan the array for each element, leading to quadratic time, which quickly becomes infeasible for large streams of acoustic data. The optimal paradigm leverages a hash‑based set (or map) to record which values have already been seen; as we iterate once through the array, we check membership in O(1) average time and emit the element only if it is unseen. This single‑pass, hash‑set approach reduces the overall complexity from O(n²) to O(n) while using O(k) extra space, where k is the number of distinct frequencies.
Why the hash set works so well lies in the properties of average‑case constant‑time look‑ups and insertions provided by modern hash table implementations. By decoupling the "have we seen this value?" question from the linear scan, we avoid repeated comparisons and can handle input sizes in the millions without performance degradation. The algorithm thus exemplifies the broader principle of using auxiliary data structures to transform a seemingly quadratic problem into a linear one.
Interview Questions on This Problem
Q1How would you return the list of unique integers from an array while preserving their original order?
Iterate once through the array, maintain a hash set of seen values, and append an element to the result list only if it is not already in the set. This yields O(n) time and O(k) extra space.
Q2What are the trade‑offs between using a hash set versus a sorted data structure (e.g., TreeSet) for this problem?
A hash set offers average O(1) insert and lookup, giving linear overall time, but does not maintain order; we preserve order manually via the result list. A TreeSet provides O(log n) operations and keeps elements sorted, which is unnecessary here and adds overhead, increasing time to O(n log n).
Q3If the input array is extremely large and cannot fit into memory, how could you adapt the algorithm?
Process the stream in chunks, using an external hash set stored on disk or a Bloom filter for approximate membership, and write out unique elements as they appear. This trades exactness for memory efficiency, or you can use a two‑pass approach with external sorting if exact uniqueness is required.
Examples
Input
[4, 2, 4, 7, 2, 9, 7, 1]
Output
[4, 2, 7, 9, 1]
Explanation: 1. Start with an empty result list and a set to track seen values. 2. Process 4: Not seen. Add to result and seen set. Result: [4]. 3. Process 2: Not seen. Add to result and seen set. Result: [4, 2]. 4. Process 4: Already seen. Skip. 5. Process 7: Not seen. Add to result and seen set. Result: [4, 2, 7]. 6. Process 2: Already seen. Skip. 7. Process 9: Not seen. Add to result and seen set. Result: [4, 2, 7, 9]. 8. Process 7: Already seen. Skip. 9. Process 1: Not seen. Add to result and seen set. Result: [4, 2, 7, 9, 1]. 10. Return [4, 2, 7, 9, 1].
Input
[10, 10, 10, 10]
Output
[10]
Explanation: 1. Process 10: Not seen. Add to result and seen set. Result: [10]. 2. Process 10: Already seen. Skip. 3. Process 10: Already seen. Skip. 4. Process 10: Already seen. Skip. 5. Return [10].
Input
[5, 3, 8, 1, 5, 3, 8, 1, 2]
Output
[5, 3, 8, 1, 2]
Explanation: 1. Process 5: Not seen. Result: [5]. 2. Process 3: Not seen. Result: [5, 3]. 3. Process 8: Not seen. Result: [5, 3, 8]. 4. Process 1: Not seen. Result: [5, 3, 8, 1]. 5. Process 5: Already seen. Skip. 6. Process 3: Already seen. Skip. 7. Process 8: Already seen. Skip. 8. Process 1: Already seen. Skip. 9. Process 2: Not seen. Result: [5, 3, 8, 1, 2]. 10. Return [5, 3, 8, 1, 2].
Input
[]
Output
[]
Explanation: 1. The input array is empty. 2. No elements to process. 3. Return an empty list.
Constraints
- 0 <= signals.length <= 10^5
- -10^9 <= signals[i] <= 10^9
- The output list must preserve the order of first occurrences.
- Time complexity should be O(n) where n is the length of the input array.
- Space complexity should be O(n) to store the seen values and the result.
Optimal Approach & Strategy
Traverse once, using a hash set to record seen values; append to the result only when the current value is not in the set, achieving O(n) time.
Brute Force Approach
For each element, scan the entire prefix to see if it appeared before; if not, add it to the result. This requires O(n²) time.
Verified Code Solutions
function solution(nums) { let seen = new Set(); let result = []; for (let num of nums) { if (!seen.has(num)) { result.push(num); seen.add(num); } } return result; }class Solution { public: vector<int> solution(vector<int>& nums) { unordered_set<int> seen; vector<int> result; for (int num : nums) { if (seen.find(num) == seen.end()) { result.push_back(num); seen.insert(num); } } return result; } }import java.util.*; class Solution { public int[] solution(int[] nums) { Set<Integer> seen = new HashSet<>(); List<Integer> result = new ArrayList<>(); for (int num : nums) { if (!seen.contains(num)) { result.add(num); seen.add(num); } } int[] arr = new int[result.size()]; for (int i = 0; i < result.size(); i++) { arr[i] = result.get(i); } return arr; } }def solution(nums): seen = set(); result = []; for num in nums: if num not in seen: result.append(num); seen.add(num); return resultfunction solution(nums) { let seen = new Set(); let result = []; for (let num of nums) { if (!seen.has(num)) { result.push(num); seen.add(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.