Safety Mechanism: The Hidden Guard
The Concern
Looking at this code:
// Option 1: EXTEND existing subsequence
if (need.getOrDefault(x, 0) > 0) {
freq.put(x, freq.get(x) - 1); // ← What if freq[x] is 0 or doesn't exist?
need.put(x, need.get(x) - 1);
need.put(x + 1, need.getOrDefault(x + 1, 0) + 1);
}
The question: We check if there's DEMAND for x (via need[x]), but we don't seem to check if there's SUPPLY of x (via freq[x]). What if freq[x] doesn't exist or is already 0?
The Three-Layer Protection System
The algorithm has THREE layers that guarantee freq[x] > 0 before we use it.
Layer 1: Loop Through Actual Array Numbers
for (int x : nums) { // ← We only see numbers that exist in the input
What this means:
- If a number doesn't exist in the input array, we never process it
- We only iterate through numbers that were actually provided
Example:
Input: [1, 2, 3, 5, 6, 7]
Numbers we process: 1, 2, 3, 5, 6, 7
Number we DON'T process: 4 (doesn't exist in input)
The loop structure prevents us from even trying to use numbers that don't exist.
Layer 2: The Guard Check
int fx = freq.getOrDefault(x, 0);
if (fx == 0) continue; // ← Skip if x is already used up
What this means:
- Before doing ANYTHING with
x, we check if supply remains - If
freq[x] == 0, we skip to the next number - We never reach the EXTEND or START logic if supply is exhausted
Example:
Input: [1, 2, 3, 3, 4, 5]
↑ ↑
first second
Iteration 1: Process first 3
- freq[3] = 2 (two copies available)
- Pass guard check ✓
- Use it: freq[3] becomes 1
Iteration 2: Process second 3
- freq[3] = 1 (one copy remains)
- Pass guard check ✓
- Use it: freq[3] becomes 0
Iteration 3: If we somehow process 3 again
- freq[3] = 0 (no copies left)
- Guard check FAILS ✓
- Skip to next number (never reach EXTEND logic)
Layer 3: Initial Frequency Map
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}
What this means:
- Every number in the array is counted upfront
- If
xappears innums, thenfreq[x]exists and starts > 0
Complete Code Structure
Here's how the layers work together:
// LAYER 3: Build frequency map
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}
Map<Integer, Integer> need = new HashMap<>();
// LAYER 1: Loop through actual numbers
for (int x : nums) {
// LAYER 2: Guard check
int fx = freq.getOrDefault(x, 0);
if (fx == 0) continue; // Skip if already used
// NOW IT'S SAFE: We know x exists and freq[x] > 0
if (need.getOrDefault(x, 0) > 0) {
freq.put(x, freq.get(x) - 1); // SAFE!
need.put(x, need.get(x) - 1);
need.put(x + 1, need.getOrDefault(x + 1, 0) + 1);
}
else if (freq.getOrDefault(x + 1, 0) > 0 &&
freq.getOrDefault(x + 2, 0) > 0) {
freq.put(x, freq.get(x) - 1); // SAFE!
freq.put(x + 1, freq.get(x + 1) - 1);
freq.put(x + 2, freq.get(x + 2) - 1);
need.put(x + 3, need.getOrDefault(x + 3, 0) + 1);
}
else {
return "fail";
}
}
Detailed Trace
Let's trace [1, 2, 3, 3, 4, 5]:
Initial State
freq = {1:1, 2:1, 3:2, 4:1, 5:1}
need = {}
Processing x = 1
LAYER 1: x = 1 (from array)
LAYER 2: freq[1] = 1, guard passes ✓
Check EXTEND: need[1] = 0 (no demand)
Check START: freq[2] = 1 ✓, freq[3] = 2 ✓
Action: START [1,2,3]
freq[1]-- → freq = {1:0, 2:0, 3:1, 4:1, 5:1}
freq[2]--
freq[3]--
need[4]++ → need = {4:1}
Processing x = 2
LAYER 1: x = 2 (from array)
LAYER 2: freq[2] = 0, guard FAILS ✗
Action: SKIP (already used)
Processing x = 3 (first)
LAYER 1: x = 3 (from array)
LAYER 2: freq[3] = 1, guard passes ✓
Check EXTEND: need[3] = 0 (no demand)
Check START: freq[4] = 1 ✓, freq[5] = 1 ✓
Action: START [3,4,5]
freq[3]-- → freq = {1:0, 2:0, 3:0, 4:0, 5:0}
freq[4]--
freq[5]--
need[6]++ → need = {4:1, 6:1}
Processing x = 3 (second)
LAYER 1: x = 3 (from array)
LAYER 2: freq[3] = 0, guard FAILS ✗
Action: SKIP (both 3's already used)
Processing x = 4, x = 5
LAYER 2: freq[4] = 0, guard FAILS ✗
LAYER 2: freq[5] = 0, guard FAILS ✗
Action: SKIP (already used)
The Key Insight
The guard check creates a safety invariant:
By the time we execute
freq.put(x, freq.get(x) - 1), we have ALREADY verified thatfreq[x] > 0.
The three layers work together:
- We only process numbers from the input (Layer 1)
- We only continue if supply exists (Layer 2)
- Supply was initialized correctly (Layer 3)
Result: It's impossible to access freq[x] when x doesn't exist or when freq[x] is 0.
What If We Removed the Guard?
for (int x : nums) {
// REMOVED: if (freq[x] == 0) continue;
if (need.getOrDefault(x, 0) > 0) {
freq.put(x, freq.get(x) - 1); // BUG!
}
}
This would break:
Input: [1, 2, 3, 3, 4, 5]
Process x=3 (first):
- Use one 3: freq[3] = 2 → 1
Process x=3 (second):
- Without guard, process again
- Use one 3: freq[3] = 1 → 0
If somehow we need to process 3 again:
- Without guard, would try: freq[3] = 0 → -1 ← INVALID!
The guard prevents multiple uses of the same occurrence.
Visual Representation
Input: [1, 2, 3, 3, 4, 5]
┌─────────────────────────────────┐
│ LAYER 1: Loop through array │
│ → Only see numbers that exist │
└────────────┬────────────────────┘
│
↓
┌─────────────────────────────────┐
│ LAYER 2: Check freq[x] > 0 │
│ → Only process if supply remains│
└────────────┬────────────────────┘
│
↓
┌─────────────────────────────────┐
│ LAYER 3: Use freq[x] │
│ → Safe! We know it exists & > 0 │
└─────────────────────────────────┘
Summary
The concern: "We check demand (need[x]), but what if we don't have supply (freq[x])?"
The answer: Three layers of protection ensure freq[x] > 0:
- Loop structure - Only process numbers from the input array
- Guard check - Only continue if
freq[x] > 0 - Initial setup - All input numbers are counted in
freq
The guarantee: By the time we execute freq.get(x) - 1, we KNOW:
xexists in the inputfreq[x] > 0- The operation is safe
The guard check isn't just optimization—it's a correctness guarantee that prevents:
- Using numbers more times than they appear
- Accessing non-existent entries
- Invalid negative frequencies