Unique Identifier Counter — Problem Statement & Solution Guide
Problem Description
Given an unsorted array of integers, determine the smallest positive integer (greater than zero) that is not present in the array. The algorithm must run in linear time relative to the array length and may only use a constant amount of additional memory beyond the input storage. Return the missing integer as the result.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Unique Identifier Counter"
WHY DOES IT MATTER?
This pattern teaches how to repurpose input storage as an implicit hash table, a technique that appears in many low‑level system problems where memory is at a premium.
OPTIMIZATION CHALLENGE
Recognizing that the missing integer is bounded by n+1 lets you limit the domain and safely overwrite the array, turning a seemingly O(n log n) problem into pure linear time with constant extra space.
REAL-WORLD CONNECTION
Think of a distributed key‑value store that shards data based on a modulo of the key; placing each key in its bucket mirrors the index‑mapping step, ensuring O(1) lookup without extra metadata.
During an interview, first verbalize the bound [1,n+1], then describe the in‑place swapping loop; a quick dry‑run on a small example often convinces the interviewer you understand the core invariant.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The classic solution relies on the fact that the answer must lie in the range [1, n+1] where n is the length of the array. By rearranging the array in‑place so that each positive value v (1 ≤ v ≤ n) is placed at index v‑1, we transform the problem into a simple scan for the first index i where a[i] ≠ i+1. Naïve methods such as sorting (O(n log n)) or using a hash set (O(n) time but O(n) extra space) break the linear‑time/constant‑space contract for very large inputs, because the hidden constants or memory overhead become prohibitive. The optimal paradigm—often called “cyclic sort” or “index‑mapping”—exploits the array itself as a hash table, achieving O(n) time while using only O(1) additional memory beyond the input buffer.
Interview Questions on This Problem
Q1How would you modify the algorithm if the array could contain duplicate values and you still need the smallest missing positive?
The in‑place placement loop must skip swapping when the target position already holds the correct value (i.e., a[i]==a[a[i]-1]) to avoid infinite cycles caused by duplicates; after the placement phase the scan logic remains unchanged.
Q2What is the time‑space trade‑off if you are allowed O(n) extra memory?
You could use a boolean bitmap of size n+1 to mark presence of each integer in O(n) time and O(n) space, then scan the bitmap for the first false entry, which is simpler but violates the constant‑space requirement.
Q3Why does the answer never exceed n+1, even if the array contains large positive numbers?
With n slots you can at most place the numbers 1…n; if all those are present, the smallest missing positive is n+1. Any value >n cannot affect the answer because it cannot occupy a required index.
Examples
Input
[3,4,-1,1]
Output
2
Explanation: The positive numbers in the array are 1,3,4. The smallest positive integer not seen is 2, so the answer is 2.
Input
[1,2,0]
Output
3
Explanation: The array contains 1 and 2 as the only positive values. The next positive integer, 3, does not appear, therefore the output is 3.
Input
[7,8,9,11,12]
Output
1
Explanation: No positive integer less than 7 is present. The smallest missing positive integer is therefore 1.
Constraints
- 1 <= nums.length <= 200000
- -10^9 <= nums[i] <= 10^9
- Required time complexity: O(n)
- Allowed extra space: O(1) (excluding the input array)
Optimal Approach & Strategy
Rearrange the array in‑place so each value v (1≤v≤n) sits at index v‑1, then scan once to locate the first mismatched position.
Brute Force Approach
Sort the array or insert every element into a hash set then iterate from 1 upward until you find a missing number.
Verified Code Solutions
function firstMissingPositive(nums) {
const n = nums.length;
for(let i=0;i<n;i++){
while(nums[i]>=1 && nums[i]<=n && nums[nums[i]-1]!==nums[i]){
const correctIdx = nums[i]-1;
[nums[i], nums[correctIdx]] = [nums[correctIdx], nums[i]];
}
}
for(let i=0;i<n;i++){
if(nums[i]!==i+1) return i+1;
}
return n+1;
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length){
const n = input[0];
const nums = input.slice(1, n+1);
console.log(firstMissingPositive(nums));
}#include <bits/stdc++.h>
using namespace std;
int firstMissingPositive(vector<int> nums) {
int n = nums.size();
for(int i=0;i<n;++i){
while(nums[i]>=1 && nums[i]<=n && nums[nums[i]-1]!=nums[i]){
swap(nums[i], nums[nums[i]-1]);
}
}
for(int i=0;i<n;++i){
if(nums[i]!=i+1) return i+1;
}
return n+1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0; vector<int> a(n); for(int i=0;i<n;++i)cin>>a[i];
cout<<firstMissingPositive(a);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static int firstMissingPositive(int[] nums) {
int n = nums.length;
for(int i=0;i<n;i++){
while(nums[i]>=1 && nums[i]<=n && nums[nums[i]-1]!=nums[i]){
int correctIdx = nums[i]-1;
int temp = nums[i];
nums[i] = nums[correctIdx];
nums[correctIdx] = temp;
}
}
for(int i=0;i<n;i++){
if(nums[i]!=i+1) return i+1;
}
return n+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;
StringTokenizer st = new StringTokenizer(line);
int n = Integer.parseInt(st.nextToken());
int[] nums = new int[n];
int idx = 0;
while(idx < n){
if(!st.hasMoreTokens()){
line = br.readLine();
if(line == null) break;
st = new StringTokenizer(line);
continue;
}
nums[idx++] = Integer.parseInt(st.nextToken());
}
System.out.print(firstMissingPositive(nums));
}
}def first_missing_positive(nums):
n = len(nums)
i = 0
while i < n:
val = nums[i]
if 1 <= val <= n and nums[val-1] != val:
nums[i], nums[val-1] = nums[val-1], nums[i]
else:
i += 1
for idx, val in enumerate(nums, 1):
if val != idx:
return idx
return n+1
if __name__ == "__main__":
import sys
data = list(map(int, sys.stdin.read().strip().split()))
if data:
n = data[0]
nums = data[1:1+n]
print(first_missing_positive(nums))function firstMissingPositive(nums) {
const n = nums.length;
for(let i=0;i<n;i++){
while(nums[i]>=1 && nums[i]<=n && nums[nums[i]-1]!==nums[i]){
const correctIdx = nums[i]-1;
[nums[i], nums[correctIdx]] = [nums[correctIdx], nums[i]];
}
}
for(let i=0;i<n;i++){
if(nums[i]!==i+1) return i+1;
}
return n+1;
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length){
const n = input[0];
const nums = input.slice(1, n+1);
console.log(firstMissingPositive(nums));
}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.