Unique Identifier Allocation — Problem Statement & Solution Guide
Problem Description
Given an integer array identifierList, produce a new integer array of identical length. For each index i, the output value is 1 if identifierList[i] has not appeared at any earlier position (j < i); otherwise the output value is 0. The algorithm must examine the array in order and decide for each element whether it is a first‑time occurrence.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Unique Identifier Allocation"
WHY DOES IT MATTER?
Detecting first occurrences underpins duplicate removal, event de‑duplication, and cache‑hit tracking, all of which are fundamental in high‑throughput systems.
OPTIMIZATION CHALLENGE
The key insight is to replace the O(n) per‑element search with an O(1) hash‑based membership test, turning quadratic work into linear work.
REAL-WORLD CONNECTION
Think of a web analytics pipeline that flags a user’s first visit to a page; the pipeline must decide in real time whether the user‑page pair has been seen before, exactly like this array scan.
During an interview, write the set‑based solution first, then discuss edge cases (negative numbers, large value ranges) and possible bitmap optimizations to show depth.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem is a classic instance of detecting first‑time occurrences while scanning an array from left to right. A naïve solution would compare each element with all previous elements, leading to O(n²) time, which quickly becomes infeasible for large n (e.g., n ≈ 10⁶). The optimal paradigm leverages a constant‑time membership test by storing already‑seen identifiers in a hash‑based set (or boolean bitmap when the value range is bounded). As we iterate, we query the set: if the element is absent we emit 1 and insert it; otherwise we emit 0. This yields linear time because each element triggers at most one hash lookup and one insertion, both O(1) on average. The auxiliary space is O(k), where k is the number of distinct identifiers (≤ n).
Interview Questions on This Problem
Q1How would you adapt the solution to also return the index of the first occurrence for each element?
Maintain a hash map from identifier to its first index; when you encounter a value for the first time, store i in the map and output 1, otherwise output 0 and ignore the map entry.
Q2What changes are needed if the identifiers are guaranteed to be in the range [0, 10⁶]?
Instead of a hash set you can allocate a boolean array of size 10⁶+1, giving O(1) look‑ups with lower constant factors and O(range) space.
Q3Explain how you would solve the problem in a streaming context where the array cannot be fully loaded into memory.
Use an external hash set (e.g., a Bloom filter for approximate membership) or a disk‑backed hash table; the algorithm remains the same—process each incoming identifier, emit 1 if unseen, then record it.
Examples
Input
[5,3,5,2,3,7]
Output
[1,1,0,1,0,1]
Explanation: Index 0: 5 has not been seen → 1. Index 1: 3 new → 1. Index 2: 5 already seen at index 0 → 0. Index 3: 2 new → 1. Index 4: 3 already seen at index 1 → 0. Index 5: 7 new → 1.
Input
[10]
Output
[1]
Explanation: The single element 10 has no prior occurrence, so the result is 1.
Input
[-1,-1,-2,-1,0]
Output
[1,0,1,0,1]
Explanation: Index 0: -1 first time → 1. Index 1: -1 repeat → 0. Index 2: -2 first time → 1. Index 3: -1 repeat → 0. Index 4: 0 first time → 1.
Constraints
- 1 <= identifierList.length <= 100000
- -1000000000 <= identifierList[i] <= 1000000000
- Expected time complexity: O(n)
- Expected auxiliary space: O(n)
Optimal Approach & Strategy
Maintain a hash set of seen identifiers. While iterating, check set membership: emit 1 and insert when unseen, emit 0 otherwise. This runs in linear time.
Brute Force Approach
For each index i, loop over all j < i and compare identifierList[i] with identifierList[j]; if any match is found output 0, else output 1. This requires two nested loops.
Verified Code Solutions
'use strict';
function uniqueIdentifierAllocation(identifierList){
const seen=new Set();
const result=[];
for(const x of identifierList){
if(seen.has(x)){
result.push(0);
}else{
result.push(1);
seen.add(x);
}
}
return result;
}
function main(){
const fs=require('fs');
const data=fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
const n=data[0];
const arr=data.slice(1,1+n);
const res=uniqueIdentifierAllocation(arr);
console.log(res.join(' '));
}
main();#include <bits/stdc++.h>
using namespace std;
vector<int> uniqueIdentifierAllocation(const vector<int>& identifierList){
unordered_set<int> seen;
vector<int> result;
result.reserve(identifierList.size());
for(int x:identifierList){
if(seen.find(x)==seen.end()){
result.push_back(1);
seen.insert(x);
}else{
result.push_back(0);
}
}
return result;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> arr(n);
for(int i=0;i<n;++i) cin>>arr[i];
vector<int> res=uniqueIdentifierAllocation(arr);
for(size_t i=0;i<res.size();++i){
if(i) cout<<' ';
cout<<res[i];
}
cout<<"\n";
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static int[] uniqueIdentifierAllocation(int[] identifierList) {
Set<Integer> seen = new HashSet<>();
int[] result = new int[identifierList.length];
for(int i=0;i<identifierList.length;i++){
int x = identifierList[i];
if(seen.contains(x)){
result[i]=0;
}else{
result[i]=1;
seen.add(x);
}
}
return result;
}
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[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) arr[i]=Integer.parseInt(st.nextToken());
int[] res = uniqueIdentifierAllocation(arr);
StringBuilder sb = new StringBuilder();
for(int i=0;i<res.length;i++){
if(i>0) sb.append(' ');
sb.append(res[i]);
}
System.out.println(sb.toString());
}
}import sys
def uniqueIdentifierAllocation(identifierList):
seen=set()
result=[]
for x in identifierList:
if x in seen:
result.append(0)
else:
result.append(1)
seen.add(x)
return result
def main():
data=sys.stdin.read().strip().split()
if not data:
return
n=int(data[0])
arr=list(map(int,data[1:1+n]))
res=uniqueIdentifierAllocation(arr)
print(' '.join(map(str,res)))
if __name__=='__main__':
main()'use strict';
function uniqueIdentifierAllocation(identifierList){
const seen=new Set();
const result=[];
for(const x of identifierList){
if(seen.has(x)){
result.push(0);
}else{
result.push(1);
seen.add(x);
}
}
return result;
}
function main(){
const fs=require('fs');
const data=fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
const n=data[0];
const arr=data.slice(1,1+n);
const res=uniqueIdentifierAllocation(arr);
console.log(res.join(' '));
}
main();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.