Definition
- Bounded answer – in an array of length n, the smallest missing positive must lie in the range 1 to n+1, so values outside this window are irrelevant.
- Cyclic sort placement – each value v in range 1 to n is placed at index v-1, treating the array itself as a presence hash table.
- Skip guard – negatives, zeros, values greater than n, and duplicates already at their home index are skipped during placement.
- Scan phase – after placement, the first index where the stored value is not index+1 reveals the smallest missing positive.
- Fallback – if every slot is correctly filled, the answer is n+1.
The National Bank of India issues positive queue tokens numbered from 1 upward. Customers hold assorted tokens including invalid ones, duplicates, and negative placeholders. The clerk files every valid token into its matching slot and then walks the slots from the beginning. The first empty slot number is the next token to issue.
Understanding the Concepts
What is the Smallest Missing Positive problem?
Given an unsorted array that may contain duplicates, negatives, and zero, find the smallest positive integer starting from 1 that does not appear in the array. The constraint is O(n) time and O(1) extra space, which rules out sorting (O(n log n)) and hash sets (O(n) space).
package com.bank.token;
public class SmallestMissingPositive {
public static int findSmallest(int[] tokens) {
int n = tokens.length;
// Phase 1: Cyclic placement
for (int i = 0; i < n; i++) {
while (tokens[i] > 0 && tokens[i] <= n
&& tokens[i] != tokens[tokens[i] - 1]) {
int target = tokens[i] - 1;
int temp = tokens[i];
tokens[i] = tokens[target];
tokens[target] = temp;
}
}
// Phase 2: Scan for first mismatch
for (int i = 0; i < n; i++) {
if (tokens[i] != i + 1) return i + 1;
}
return n + 1;
}
}
Why is the answer bounded to 1..n+1?
An array of length n can hold at most n distinct positive integers. If those are exactly 1, 2, 3, ..., n, then the smallest missing positive is n+1. If any of those is missing, the answer is less than or equal to n. Either way, the answer lies in 1 to n+1. This bounded answer is the insight that makes the in-place approach possible: you only need n slots to track which of the first n positive integers are present.
package com.bank.token;
public class BoundedAnswerDemo {
public static void demonstrate() {
// Array [1, 2, 3]: all present, answer is 4 (n+1)
// Array [3, 4, -1, 1]: missing 2, answer is 2
// Array [7, 8, 9, 11]: none of 1..4 present, answer is 1
System.out.println(findSmallest(new int[]{1, 2, 3})); // 4
System.out.println(findSmallest(new int[]{3, 4, -1, 1})); // 2
System.out.println(findSmallest(new int[]{7, 8, 9, 11})); // 1
}
private static int findSmallest(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++)
while (a[i] > 0 && a[i] <= n && a[i] != a[a[i] - 1]) {
int t = a[i] - 1; int tmp = a[i]; a[i] = a[t]; a[t] = tmp;
}
for (int i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;
return n + 1;
}
}
4
2
1
How does cyclic sort place values at their home index?
For each position i, if the value tokens[i] is a positive integer in the range 1 to n and it is not already at its home index (tokens[i] - 1), swap it to its home. Repeat this while loop until the value at position i is either out of range or already home. The while loop ensures that each swap puts at least one value at its correct home, so the total number of swaps across all iterations is at most n.
package com.bank.token;
public class CyclicPlacementTrace {
public static void trace() {
int[] tokens = {3, 4, -1, 1};
// i=0: tokens[0]=3, home index=2, swap with tokens[2]
// tokens = [-1, 4, 3, 1]
// tokens[0]=-1, out of range, stop
// i=1: tokens[1]=4, home index=3, swap with tokens[3]
// tokens = [-1, 1, 3, 4]
// tokens[1]=1, home index=0, swap with tokens[0]
// tokens = [1, -1, 3, 4]
// tokens[1]=-1, out of range, stop
// i=2: tokens[2]=3, home index=2, already home, stop
// i=3: tokens[3]=4, home index=3, already home, stop
// Result: [1, -1, 3, 4]
// Scan: index 1 has -1 != 2, so answer is 2
}
}
What values are skipped during placement?
The placement guard tokens[i] > 0 && tokens[i] <= n && tokens[i] != tokens[tokens[i] - 1] skips three categories of values. Negatives and zeros are skipped because they cannot be the answer. Values greater than n are skipped because the answer is at most n+1. Duplicates where the home index already holds the same value are skipped to prevent infinite loops.
package com.bank.token;
public class SkipGuardDemo {
public static void showSkips() {
int[] tokens = {-5, 0, 3, 3, 7, 1};
int n = 6;
// -5: negative, skip
// 0: zero, skip
// 3: in range, place at index 2
// 3: duplicate, tokens[2] already has 3, skip
// 7: greater than n=6, skip
// 1: in range, place at index 0
// After placement: [1, 0, 3, 3, 7, -5]
// Scan: index 1 has 0 != 2, answer is 2
}
}
What are edge cases?
Edge cases include an empty array (answer is 1), an array of all negatives (answer is 1), an array with a perfect sequence from 1 to n (answer is n+1), and an array with all duplicates of the same value.
package com.bank.token;
public class EdgeCases {
public static void test() {
System.out.println(findSmallest(new int[]{})); // 1 (empty)
System.out.println(findSmallest(new int[]{-1, -2, -3})); // 1 (all negative)
System.out.println(findSmallest(new int[]{1, 2, 3, 4})); // 5 (perfect)
System.out.println(findSmallest(new int[]{2, 2, 2, 2})); // 1 (all duplicates)
}
private static int findSmallest(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++)
while (a[i] > 0 && a[i] <= n && a[i] != a[a[i] - 1]) {
int t = a[i] - 1; int tmp = a[i]; a[i] = a[t]; a[t] = tmp;
}
for (int i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;
return n + 1;
}
}
1
1
5
1
What is the time and space complexity?
Time is O(n). Each element is swapped at most once to its home index, so the total number of swaps across all while-loop iterations is at most n. The scan phase is another O(n). Space is O(1) extra because the array itself serves as the hash table.
| Approach | Time | Space | Notes |
|---|---|---|---|
| Sorting then scanning | O(n log n) | O(1) | Not optimal |
| Hash set | O(n) | O(n) | Extra space |
| Cyclic sort in-place | O(n) | O(1) | Optimal |
What are common mistakes?
The most common mistake is not handling duplicates, which causes an infinite swap loop. If tokens[i] equals tokens[tokens[i] - 1], both positions hold the same value, and swapping them changes nothing, so the while loop never terminates.
package com.bank.token;
public class CommonMistake {
// WRONG: infinite loop on duplicates
public static int wrongVersion(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
// BUG: missing duplicate guard
while (a[i] > 0 && a[i] <= n && a[i] != i + 1) {
int t = a[i] - 1;
int tmp = a[i]; a[i] = a[t]; a[t] = tmp;
// If a[i] == a[t], swapping changes nothing => infinite loop!
}
}
for (int i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;
return n + 1;
}
// CORRECT: check a[i] != a[a[i]-1] to avoid infinite loop
public static int correctVersion(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
while (a[i] > 0 && a[i] <= n && a[i] != a[a[i] - 1]) {
int t = a[i] - 1;
int tmp = a[i]; a[i] = a[t]; a[t] = tmp;
}
}
for (int i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;
return n + 1;
}
}
How is this used in a banking context?
At the National Bank of India, branch token dispensers maintain an in-memory pool of returned, cancelled, and duplicated token values mixed with negative placeholders. Issuing the next token means finding the smallest positive number not currently held, without allocating a separate data structure over a large pool. The cyclic sort approach files valid tokens at their home index and returns the first empty slot in linear time and constant space.
package com.bank.token;
public class TokenDispenser {
private int[] tokenPool;
public TokenDispenser(int[] existingTokens) {
this.tokenPool = existingTokens.clone();
}
public int issueNextToken() {
return SmallestMissingPositive.findSmallest(tokenPool);
}
public static void main(String[] args) {
int[] pool = {3, 4, -1, 1};
TokenDispenser dispenser = new TokenDispenser(pool);
System.out.println("Next token to issue: " + dispenser.issueNextToken());
}
}
Next token to issue: 2
Visual Overview
Cyclic Sort Placement
=====================
Input: [3, 4, -1, 1]
Goal: Place value v at index v-1
Step 1 (i=0): tokens[0]=3, home=2
Swap tokens[0] <-> tokens[2]
[3, 4, -1, 1] → [-1, 4, 3, 1]
tokens[0]=-1 → out of range, stop
Step 2 (i=1): tokens[1]=4, home=3
Swap tokens[1] <-> tokens[3]
[-1, 4, 3, 1] → [-1, 1, 3, 4]
tokens[1]=1, home=0
Swap tokens[1] <-> tokens[0]
[-1, 1, 3, 4] → [1, -1, 3, 4]
tokens[1]=-1 → out of range, stop
Step 3 (i=2): tokens[2]=3, home=2 → already home
Step 4 (i=3): tokens[3]=4, home=3 → already home
Result: [1, -1, 3, 4]
↑ ↑ ↑ ↑
1 ? 3 4
Scan:
Index 0: 1 == 0+1 ✓
Index 1: -1 != 1+1 → Answer: 2
Answer Window
=============
Array length n = 4
Possible answers: {1, 2, 3, 4, 5}
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ ← slots for values 1..n
└───┴───┴───┴───┘
If all filled → answer is n+1 = 5
First empty slot → answer
Key Takeaway
Finding the smallest missing positive integer in a messy array that may hold negatives, zeros, duplicates, and out-of-range values is the hard variant of cyclic sort, and the insight that unlocks it is the bounded answer. In an array of length n, the answer must lie in the range 1 to n+1, because the array can hold at most n distinct positive integers. That means any value outside the 1-to-n window is irrelevant, which lets you treat the array itself as a presence hash table using no extra memory.
You run one placement pass that sends each in-range positive value to the index equal to the value minus one, skipping negatives, zeros, values greater than n, and duplicates already at their home index. The while loop at each position ensures every swap puts at least one value home, so the total work is linear. Then you scan for the first index whose stored value is not index plus one and return that index plus one, or n+1 if every slot is correct.
At the National Bank of India, Rajesh built a token dispenser for the branch queue system. The in-memory token pool accumulated returned, cancelled, and duplicated token values along with negative placeholders. Issuing the next token meant finding the smallest positive number not currently held, and the cyclic sort approach solved it in O(n) time and O(1) space without allocating a separate data structure.
The most critical implementation detail is the duplicate guard: you must check that tokens[i] != tokens[tokens[i] - 1] before swapping, because if both positions hold the same value, swapping changes nothing and the while loop runs forever.
Remember one sentence: place each in-range positive at its home index with cyclic sort, then the first empty home is the smallest missing positive.
---