New 21 Game – Probability Explained with Sliding Window

Difficulty: Medium
Topics: Dynamic Programming, Probability, Sliding Window

🧠 Problem Understanding (In Simple Words)

Alice is playing a game where she keeps drawing points randomly.

Here’s how it works:

• She starts with 0 points
• Each time, she draws a number between 1 and maxPts
• She keeps drawing until her total becomes at least k

👉 Your goal: Find the probability that her final score is less than or equal to n

💡 Intuition (How to Think About It)

This is not a typical problem — it’s about probability accumulation.

Think of it like:

👉 At every step, Alice has multiple possible scores
👉 Each score has a probability
👉 We need to track how these probabilities evolve

🎯 Key Observation

• Once Alice reaches k or more points, she stops
• So final scores will always be in range:

  [k, k + maxPts - 1]
  

👉 We only care about: Which of these final scores are ≤ n

🚀 Approach (High-Level)

We use Dynamic Programming:

1. Let dp[i] = probability of getting exactly i points
2. Start with:

   dp[0] = 1 (100% probability)
   

3. For each score:
   • Add probability from previous states
   • Maintain a sliding window to optimize calculation

⚡ Optimization Insight (Sliding Window)

Instead of recalculating probabilities again and again:

👉 Maintain a running sum of last maxPts values

This reduces time complexity significantly.

🎯 Visualization Using DrawToCode

This problem becomes much easier when visualized:

• Each state represents a possible score
• Arrows show transitions between scores
• Probability flows from one state to another

👉 Using DrawToCode, you can:

• See how probability distributes across scores
• Understand why certain ranges dominate
• Debug DP transitions visually

💻 Code (Java Example)

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        if (k == 0 || n >= k + maxPts) return 1.0;

        double[] dp = new double[n + 1];
        dp[0] = 1.0;

        double windowSum = 1.0;
        double result = 0.0;

        for (int i = 1; i <= n; i++) {
            dp[i] = windowSum / maxPts;

            if (i < k) {
                windowSum += dp[i];
            } else {
                result += dp[i];
            }

            if (i - maxPts >= 0) {
                windowSum -= dp[i - maxPts];
            }
        }

        return result;
    }
}

⏱️ Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

🔍 Example Walkthrough

Input:

n = 6, k = 1, maxPts = 10

Explanation:

• Alice draws only once (since k = 1)
• Possible outcomes: 1 to 10
• Favorable outcomes: 1 to 6 → 6 cases

👉 Probability:

6 / 10 = 0.6

Input:

n = 21, k = 17, maxPts = 10

👉 Alice keeps drawing until she reaches at least 17
👉 Final scores range from 17 to 26

We calculate probability of scores ≤ 21 using DP

👉 Output:

0.73278

🧪 Edge Cases to Consider

• k = 0 → Alice never draws → probability = 1
• n >= k + maxPts → all outcomes are valid → probability = 1
• Very small ranges

🏁 Final Thought

This problem teaches:

• How to handle probabilities in DP
• Sliding window optimization
• Thinking in terms of state transitions

👉 Once you visualize probability flow, this problem becomes much easier to understand