First Occurrence of Unique Signals — Problem Statement & Solution Guide
Problem Description
You are provided with a sequence of integer values representing discrete data points collected from a monitoring system. Your task is to determine the earliest position at which each distinct value appears in the sequence. Specifically, for every unique integer in the input array, you must record the 0-based index of its first occurrence. If a value appears multiple times, only the index of the very first instance is retained; subsequent occurrences are ignored for the purpose of this mapping.
The output should be a dictionary (or map) where each key is a unique integer from the input array, and the corresponding value is the integer index of its first appearance. The order of keys in the resulting map does not matter, as it is a key-value structure. Ensure that your solution efficiently processes the array in a single pass to meet performance requirements for large inputs.
DSA Pattern Breakdown
DSA Pattern Breakdown
"First Occurrence of Unique Signals"
WHY DOES IT MATTER?
First‑occurrence tracking is a fundamental pattern for deduplication, caching, and indexing tasks where the earliest reference point matters. It teaches candidates to think in terms of stateful scans rather than repeated searches, a skill that scales to many real‑world problems.
OPTIMIZATION CHALLENGE
The key insight is to avoid nested loops by using a constant‑time membership test. By recording a value the first time it appears and ignoring later repeats, you collapse an O(n^2) problem into O(n) with only a single auxiliary data structure.
REAL-WORLD CONNECTION
Consider a distributed logging system where each unique error code should be mapped to the timestamp of its first occurrence to trigger alerts. The same hash‑map technique enables rapid identification without scanning the entire log history repeatedly.
During an interview, start by stating the naive O(n^2) idea, then immediately pivot to the hash‑map solution, emphasizing the single‑pass guarantee and discussing edge cases like empty input or all‑duplicate arrays.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The problem reduces to identifying the first position where each distinct integer appears in a linear data stream. A naive solution would scan the array for each element, resulting in O(n^2) time, which quickly becomes infeasible for large inputs because the same element is examined repeatedly. The optimal paradigm leverages a hash‑based associative container (e.g., unordered_map in C++ or dict in Python) to record the index of a value the first time it is encountered; subsequent occurrences are ignored, guaranteeing a single pass over the data. This approach exploits the average O(1) lookup and insertion time of hash tables, turning the overall complexity into linear time while using extra space proportional to the number of unique values.
Why this works is rooted in the concept of “first‑seen” tracking: as we iterate, the moment we encounter a value we check if it already exists in the map. If not, we store the current index; if it does, we skip. Because each element triggers at most one map operation, the total work scales linearly with the input size. The space overhead is bounded by the cardinality of the distinct set, which is the minimal information required to answer the query. This pattern—single‑pass hash‑map accumulation—is a staple for many frequency‑or‑position‑based problems in competitive programming and real‑world data pipelines.
Interview Questions on This Problem
Q1How would you modify the solution to return the first occurrence indices in the order of appearance of the unique values?
Maintain a vector (or list) alongside the hash map. When you insert a new value into the map, also push the value (or its index) into the vector. After the scan, iterate over the vector to output the stored indices, preserving the original order of first appearances.
Q2If the input array is sorted, can you achieve a better space complexity than O(k)?
Yes. In a sorted array, duplicate values are contiguous, so you can scan once and record the index whenever the current element differs from the previous one, using only O(1) extra space (aside from the output list). However, this only works when the sorted order is guaranteed.
Q3Explain how you would adapt the algorithm for a streaming scenario where the data cannot be stored entirely in memory.
Use a hash map to store only the first index of each value seen so far, and emit the index as soon as a new value arrives. Since you never need to revisit earlier elements, you can process the stream in constant additional memory per distinct value, discarding the raw data after processing.
Examples
Input
signals = [4, 2, 4, 7, 2, 9]
Output
{4: 0, 2: 1, 7: 3, 9: 5}Explanation: Traverse the array from left to right: 1. Index 0: Value 4 is new. Record {4: 0}. 2. Index 1: Value 2 is new. Record {4: 0, 2: 1}. 3. Index 2: Value 4 already exists. Skip. 4. Index 3: Value 7 is new. Record {4: 0, 2: 1, 7: 3}. 5. Index 4: Value 2 already exists. Skip. 6. Index 5: Value 9 is new. Record {4: 0, 2: 1, 7: 3, 9: 5}. Final map: {4: 0, 2: 1, 7: 3, 9: 5}.
Input
signals = [10, 10, 10, 10]
Output
{10: 0}Explanation: Traverse the array: 1. Index 0: Value 10 is new. Record {10: 0}. 2. Index 1: Value 10 exists. Skip. 3. Index 2: Value 10 exists. Skip. 4. Index 3: Value 10 exists. Skip. Final map: {10: 0}.
Input
signals = [5, 3, 8, 1, 5, 3, 8, 1]
Output
{5: 0, 3: 1, 8: 2, 1: 3}Explanation: Traverse the array: 1. Index 0: Value 5 is new. Record {5: 0}. 2. Index 1: Value 3 is new. Record {5: 0, 3: 1}. 3. Index 2: Value 8 is new. Record {5: 0, 3: 1, 8: 2}. 4. Index 3: Value 1 is new. Record {5: 0, 3: 1, 8: 2, 1: 3}. 5. Index 4: Value 5 exists. Skip. 6. Index 5: Value 3 exists. Skip. 7. Index 6: Value 8 exists. Skip. 8. Index 7: Value 1 exists. Skip. Final map: {5: 0, 3: 1, 8: 2, 1: 3}.
Input
signals = [-2, 0, 2, -2, 0]
Output
{-2: 0, 0: 1, 2: 2}Explanation: Traverse the array: 1. Index 0: Value -2 is new. Record {-2: 0}. 2. Index 1: Value 0 is new. Record {-2: 0, 0: 1}. 3. Index 2: Value 2 is new. Record {-2: 0, 0: 1, 2: 2}. 4. Index 3: Value -2 exists. Skip. 5. Index 4: Value 0 exists. Skip. Final map: {-2: 0, 0: 1, 2: 2}.
Constraints
- 1 <= signals.length <= 10^5
- -10^9 <= signals[i] <= 10^9
- The input array contains at least one element.
Optimal Approach & Strategy
Traverse the array once, using a hash map to store the index of a value the first time it appears; ignore later repeats, achieving O(n) time.
Brute Force Approach
For each element, scan the entire array to find its first occurrence, resulting in O(n^2) time.
Verified Code Solutions
function solution(signals) { let result = {}; for (let i = 0; i < signals.length; i++) { if (!(signals[i] in result)) { result[signals[i]] = i; } } return result; }class Solution { public: std::unordered_map<int, int> solution(std::vector<int>& signals) { std::unordered_map<int, int> result; for (int i = 0; i < signals.size(); i++) { if (result.find(signals[i]) == result.end()) { result[signals[i]] = i; } } return result; } };import java.util.HashMap; import java.util.Map; class Solution { public Map<Integer, Integer> solution(int[] signals) { Map<Integer, Integer> result = new HashMap<>(); for (int i = 0; i < signals.length; i++) { if (!result.containsKey(signals[i])) { result.put(signals[i], i); } } return result; } }def solution(signals): result = {}; for i, signal in enumerate(signals): if signal not in result: result[signal] = i; return resultfunction solution(signals) { let result = {}; for (let i = 0; i < signals.length; i++) { if (!(signals[i] in result)) { result[signals[i]] = i; } } 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.