Single Occurrence Identifier — Problem Statement & Solution Guide
Problem Description
You are given an array of integers named nums. Your task is to find the first element in the array, scanning from left to right, whose total frequency of occurrence across the entire array is exactly one.
The search must respect the initial ordering of the elements. The first integer encounter in the array that satisfies the single-occurrence condition must be selected.
If such an element is found, return its value converted to a string. If no element in nums occurs exactly once, or if the array is empty, return the string "there is no unique number".
DSA Pattern Breakdown
DSA Pattern Breakdown
"Single Occurrence Identifier"
WHY DOES IT MATTER?
Frequency aggregation combined with sequential order lookup is a core building block in data processing pipelines, text parsing, and stream analysis.
OPTIMIZATION CHALLENGE
The key insight is decoupling counting from order verification, transforming an $O(N^2)$ nested search into two sequential $O(N)$ passes.
REAL-WORLD CONNECTION
In distributed logging systems, this pattern is used to detect the first unique transaction ID in an incoming batch of out-of-order logs to identify isolated, non-retried user operations.
Always clarify edge cases early: ask what value to return if no unique element exists (e.g., -1 or null) and confirm whether elements can be negative or fit within standard integer limits.
COMPLEXITY AT A GLANCE
O(N)O(N)Core Theory — Why This Approach?
The 'Single Occurrence Identifier' problem centers on two fundamental concepts: frequency counting and preserving relative order. A naive approach inspects each element by performing a linear scan across the rest of the array to count duplicate instances. This nested search yields an $O(N^2)$ time complexity, which rapidly degrades performance on large inputs due to quadratic work scaling.
To optimize this, we decouple the frequency aggregation from the order resolution using the Hash Map pattern. A hash table allows $O(1)$ average time complexity for insertions and lookups. By storing element-to-frequency mappings in a hash map, we can aggregate counts across the entire dataset in a single $O(N)$ pass.
Once the frequency map is fully constructed, preserving order simply requires traversing the original array a second time from left to right. By checking each element's precomputed count in $O(1)$ time, the first element with a frequency of exactly one is immediately identified. This two-pass design reduces runtime complexity from $O(N^2)$ to $O(N)$ at the trade-off of $O(N)$ auxiliary space.
Interview Questions on This Problem
Q1How would you modify your solution if the input array was an endless real-time stream rather than a fixed array?
To support a streaming input where we must query the first unique element at any point in $O(1)$ time, we can combine a Hash Map with a Doubly Linked List (or a LinkedHashSet / Queue with lazy eviction). The map tracks node references and frequencies. When an element is seen for the first time, it is appended to the linked list. If seen again, it is removed from the linked list. The head of the list always points to the first unique element.
Q2If the numbers in `nums` are constrained to a small bounded range, say integers between 0 and 1000, how can you optimize the space overhead?
Instead of a generic Hash Map, which incurs dynamic memory allocations and hashing overhead, we can use a direct-address array (a fixed-size frequency array) of size 1001. This retains $O(1)$ lookup times while eliminating object overhead, improving cache locality, and reducing auxiliary memory footprint.
Q3Why is iterating over the Hash Map's entries directly after the counting pass incorrect in standard implementations?
Standard hash maps (like std::unordered_map in C++ or HashMap in Java) do not preserve insertion order. Iterating over the map's key-value pairs yields elements in arbitrary hash-bucket order rather than the original left-to-right order, violating the requirement to return the *first* occurrence.
Examples
Input
nums = [4, 5, 2, 4, 5, 9, 2]
Output
"9"
Explanation: Calculating frequencies across the array gives: 4 appears 2 times, 5 appears 2 times, 2 appears 2 times, and 9 appears 1 time. The integer 9 is the only element that appears exactly once, so it is returned as a string.
Input
nums = [12, 8, 12, 15, 8, 15]
Output
"there is no unique number"
Explanation: Calculating frequencies yields: 12 appears 2 times, 8 appears 2 times, and 15 appears 2 times. Every element has a frequency greater than 1, so the result is "there is no unique number".
Input
nums = [18, 22, 18, 9, 22, 14]
Output
"9"
Explanation: Calculating frequencies yields: 18 appears 2 times, 22 appears 2 times, 9 appears 1 time, and 14 appears 1 time. Both 9 and 14 have a frequency of 1. Because 9 appears at index 3 before 14 at index 5, 9 is returned as the first single-occurrence element.
Input
nums = []
Output
"there is no unique number"
Explanation: The array is empty, so no single-occurrence element exists.
Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Perform a single pass through nums to build a frequency count hash map. Then perform a second pass through nums in its original order, returning the first element whose map count is 1.
Brute Force Approach
For every element in the array, run a nested loop over all other elements to count its total occurrences. Return the first element whose computed count is equal to 1, resulting in $O(N^2)$ time complexity.
Verified Code Solutions
function firstSingleOccurrence(nums){
const freq = new Map();
for(const x of nums) freq.set(x,(freq.get(x)||0)+1);
for(const x of nums) if(freq.get(x)===1) return x;
return -1;
}
const fs=require('fs');
const data=fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) process.exit(0);
const n=data[0];
const nums=data.slice(1,1+n);
console.log(firstSingleOccurrence(nums).toString());#include <bits/stdc++.h>
using namespace std;
int firstSingleOccurrence(const vector<int>& nums){
unordered_map<int,int> freq;
for(int x:nums) ++freq[x];
for(int x:nums) if(freq[x]==1) return x;
return -1;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
int n; if(!(cin>>n)) return 0; vector<int> nums(n); for(int i=0;i<n;++i)cin>>nums[i];
cout<<firstSingleOccurrence(nums);
return 0;}import java.io.*;
import java.util.*;
public class Main {
public static int firstSingleOccurrence(int[] nums){
Map<Integer,Integer> freq=new HashMap<>();
for(int x:nums) freq.put(x,freq.getOrDefault(x,0)+1);
for(int x:nums) if(freq.get(x)==1) return x;
return -1;
}
public static void main(String[] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String line=br.readLine();
if(line==null||line.isEmpty()) return;
int n=Integer.parseInt(line.trim());
int[] nums=new int[n];
StringTokenizer st=new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) nums[i]=Integer.parseInt(st.nextToken());
System.out.print(firstSingleOccurrence(nums));
}
}def first_single_occurrence(nums):
from collections import Counter
freq=Counter(nums)
for x in nums:
if freq[x]==1:
return x
return -1
if __name__=="__main__":
import sys
data=sys.stdin.read().strip().split()
if not data:
sys.exit(0)
n=int(data[0])
nums=list(map(int,data[1:1+n]))
print(first_single_occurrence(nums))function firstSingleOccurrence(nums){
const freq = new Map();
for(const x of nums) freq.set(x,(freq.get(x)||0)+1);
for(const x of nums) if(freq.get(x)===1) return x;
return -1;
}
const fs=require('fs');
const data=fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) process.exit(0);
const n=data[0];
const nums=data.slice(1,1+n);
console.log(firstSingleOccurrence(nums).toString());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.