Skip to main content

Pattern 1b: Selection with Skip Constraint ⭐

Core Concept: Binary decision at each position - take it OR skip it. Taking position i forces you to skip i-1.

The Pattern​

THE MENTAL MODEL

Think of houses in a row with alarms:

  1. You can rob any house to get its value
  2. BUT robbing house i triggers alarms at houses i-1 and i+1
  3. You must skip adjacent positions
  4. Key formula: dp[i] = max(dp[i-1], dp[i-2] + value[i])

This is the dependency constraint pattern: Can't take adjacent → dp[i-2] dependency

Pattern Recognition​

WHEN YOU SEE THIS PATTERN

Keywords: "cannot take adjacent", "skip constraint", "maximize selection", "alternating"

Structure:

  • Binary choice at each position (take/skip)
  • Taking position i prevents using position i-1
  • Must look back to i-2 when taking current element
  • Max/min decision between two mutually exclusive options

State: dp[i] = best answer for range [0...i]

Key Transition:

dp[i] = Math.max(
    dp[i-1],           // Skip current element (keep previous best)
    dp[i-2] + value[i] // Take current element (skip i-1, use i-2)
)

The Constraint​

THE KEY INSIGHT

Why dp[i-2] dependency?

When you take element at position i, you gain value[i] points.

BUT you cannot use position i-1 (adjacent constraint).

Therefore, the best you can do is:

  • Use the answer from position i-2 (which is safe)
  • Add current value: dp[i-2] + value[i]

vs. skipping:

  • Keep the answer from i-1 (which may or may not include i-1)

Choose whichever is better!

Problems in This Category​

Core Problems​

  1. House Robber (LC 198) - The canonical example
  2. Delete and Earn (LC 740) - House Robber disguised with values

Pattern Variations​

  • House Robber II (LC 213) - Circular array variant
  • Maximum Alternating Subsequence Sum (LC 1911) - Alternating signs

Template Code​

public int maxWithSkipConstraint(int[] values) {
    int n = values.length;
    if (n == 0) return 0;
    if (n == 1) return values[0];

    int[] dp = new int[n];
    dp[0] = values[0];
    dp[1] = Math.max(values[0], values[1]);

    for (int i = 2; i < n; i++) {
        // Option 1: Skip current element
        int skipCurrent = dp[i-1];

        // Option 2: Take current element (must skip i-1, use i-2)
        int takeCurrent = dp[i-2] + values[i];

        // Choose better option
        dp[i] = Math.max(skipCurrent, takeCurrent);
    }

    return dp[n-1];
}

Space-Optimized Version:

public int maxWithSkipConstraintOptimized(int[] values) {
    if (values.length == 0) return 0;
    if (values.length == 1) return values[0];

    int prev2 = values[0];
    int prev1 = Math.max(values[0], values[1]);

    for (int i = 2; i < values.length; i++) {
        int current = Math.max(prev1, prev2 + values[i]);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

Key Differences from Other Patterns​

DON'T CONFUSE WITH

vs. Pattern 1a (Simple Accumulation):

  • 1a: dp[i] = dp[i-1] + dp[i-2] → ADD both (accumulate)
  • 1b: dp[i] = max(dp[i-1], dp[i-2] + value[i]) → CHOOSE one (mutually exclusive)

vs. Pattern 1c (Subarray Optimization):

  • 1b: Track global best up to position i
  • 1c: Track best ending at position i (must include current element)

The House Robber Connection​

WHY THIS IS THE "HOUSE ROBBER PATTERN"

Delete and Earn transforms into House Robber:

Given nums = [2,2,3,3,3,4]:

  1. Count points for each value:

    points[2] = 4  (two 2's)
    points[3] = 9  (three 3's)
    points[4] = 4  (one 4)

  2. Apply skip constraint:

    • Taking value 3 forces deletion of values 2 and 4
    • This is identical to: "Taking house 3 prevents robbing houses 2 and 4"

  3. Use House Robber formula:

    dp[i] = Math.max(dp[i-1], dp[i-2] + points[i])

Same pattern, different problem domain!

Common Mistakes​

PITFALLS

Mistake 1: Forgetting the constraint​

// WRONG
dp[i] = dp[i-1] + dp[i-2] + value[i];  // ❌ This is accumulation, not selection

Mistake 2: Using wrong base case​

// WRONG
dp[0] = 0;        // ❌ You can take the first element!
dp[1] = 0;        // ❌ You can take the second element!

// CORRECT
dp[0] = values[0];
dp[1] = Math.max(values[0], values[1]);

Mistake 3: Confusing "up to i" vs "ending at i"​

  • This pattern uses "up to i" (cumulative best)
  • Pattern 1c uses "ending at i" (must include current)

Learning Path​

RECOMMENDED PRACTICE

Phase 1: Master the core

  1. House Robber (LC 198) - Understand the base pattern
  2. Delete and Earn (LC 740) - Recognize the disguise

Phase 2: Variations 3. House Robber II (LC 213) - Handle circular arrays 4. Maximum Alternating Subsequence Sum (LC 1911) - Alternating signs

Key Insight: Once you see the dp[i-2] dependency, you know it's this pattern!

Next Steps​

After mastering this pattern:

  • ✅ You'll instantly recognize "adjacent constraint" → House Robber pattern
  • ✅ You'll know to look for the dp[i-2] + value[i] formula
  • ✅ You can transform problems (like Delete and Earn) into this pattern

This is one of the most common interview patterns!