LeetCode 837 - New 21 Game

In this problem, Alice repeatedly draws random numbers until her score reaches at least k. Every draw independently produces an integer between 1 and maxPts, inclusive, and each value is equally likely.

leetcodemediummathdynamic-programmingsliding-windowprobability-and-statistics

LeetCode Problem 837

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Sliding Window, Probability and Statistics

Solution

Problem Understanding

In this problem, Alice repeatedly draws random numbers until her score reaches at least k. Every draw independently produces an integer between 1 and maxPts, inclusive, and each value is equally likely.

We are asked to compute the probability that Alice's final score is less than or equal to n.

The key detail is that Alice stops drawing immediately once her score becomes at least k. That means all final scores lie in the range:

  • k to k + maxPts - 1

because the last draw can add at most maxPts.

The input parameters represent the following:

  • n is the maximum allowed final score for success.
  • k is the stopping threshold.
  • maxPts is the maximum value Alice can draw in a single turn.

The output should be a floating-point probability between 0 and 1.

The constraints are important:

  • n, k, and maxPts can all be as large as 10^4
  • This immediately rules out exponential simulation approaches.
  • We need an algorithm close to linear time.

There are several important edge cases:

  • If k == 0, Alice never draws any cards, so her score is always 0. Since 0 <= n, the answer is always 1.0.
  • If n >= k + maxPts - 1, then every possible final score is valid, so the probability is 1.0.
  • Small values of k can cause the game to terminate immediately after one draw.
  • Large ranges of possible states require careful optimization to avoid quadratic dynamic programming.

Approaches

Brute Force Approach

A straightforward approach is to model every possible sequence of draws recursively.

From a current score x < k, Alice can transition to:

  • x + 1
  • x + 2
  • ...
  • x + maxPts

each with probability 1 / maxPts.

We could recursively compute the probability of eventually ending with a valid score. This forms a probability tree.

The recurrence would look like:

  • If x >= k, return 1 if x <= n, otherwise 0
  • Otherwise, average the probabilities of all next states

This approach is correct because it exactly models the game process. However, the number of states and transitions grows extremely quickly. Even memoization still leads to an expensive transition cost because each state examines maxPts future states.

A naive DP recurrence would be:

$$dp[i] = \frac{dp[i+1] + dp[i+2] + ... + dp[i+maxPts]}{maxPts}$$

Computing this directly costs O(maxPts) per state, producing total complexity O(k * maxPts), which can reach 10^8 operations.

That is too slow for the constraints.

Optimal Approach, Dynamic Programming with Sliding Window

The key observation is that every state computes the average of a consecutive range of probabilities.

Instead of recomputing the sum every time, we maintain a sliding window.

Define:

  • dp[i] = probability of reaching score exactly i

Initially:

  • dp[0] = 1

If Alice currently has score i, then every future score from:

  • i + 1 to i + maxPts

receives probability contribution:

$$\frac{dp[i]}{maxPts}$$

However, transitions only occur while i < k.

The critical optimization is that:

$$dp[i] = \frac{windowSum}{maxPts}$$

where windowSum stores the sum of the previous maxPts DP states that can transition into i.

This converts the quadratic recurrence into linear time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(k × maxPts) or worse O(k) Recomputes large probability ranges repeatedly
Optimal O(n) O(n) Uses sliding window to maintain rolling probability sums

Algorithm Walkthrough

  1. Create a DP array dp of size n + 1.

dp[i] represents the probability that Alice reaches exactly score i. 2. Initialize the starting state.

Alice starts at score 0, so:

dp[0] = 1.0
  1. Maintain a sliding window sum.

The window represents the sum of probabilities that can transition into the current state.

Initially:

windowSum = 1.0

because only dp[0] contributes to future states at the beginning. 4. Iterate through scores from 1 to n.

For each score i:

$$dp[i] = \frac{windowSum}{maxPts}$$

This works because every previous reachable score in the window contributes equally. 5. If i < k, Alice is still allowed to draw from this state.

Therefore, dp[i] should be added into the window for future transitions. 6. If i >= k, Alice stops drawing.

This means dp[i] contributes directly to the final answer instead of future transitions. 7. Remove expired states from the window.

Once a state becomes more than maxPts behind the current index, it can no longer transition into future scores.

So when:

i >= maxPts

subtract:

dp[i - maxPts]

from the window. 8. Accumulate the answer.

Every state from k to n represents a valid stopping score.

Sum those probabilities.

Why it works

The algorithm works because every state distributes its probability uniformly across the next maxPts states. Instead of repeatedly summing the same ranges, the sliding window maintains the exact rolling total of reachable probabilities.

At every step, the window invariant is:

$$windowSum = dp[i-1] + dp[i-2] + ... + dp[i-maxPts]$$

restricted to states that are still allowed to draw. Therefore:

$$dp[i] = \frac{windowSum}{maxPts}$$

correctly computes the probability of reaching score i.

Python Solution

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k + maxPts - 1:
            return 1.0

        dp = [0.0] * (n + 1)
        dp[0] = 1.0

        window_sum = 1.0
        result = 0.0

        for score in range(1, n + 1):
            dp[score] = window_sum / maxPts

            if score < k:
                window_sum += dp[score]
            else:
                result += dp[score]

            if score >= maxPts:
                window_sum -= dp[score - maxPts]

        return result

The implementation begins with two important early exits.

If k == 0, Alice never draws, so the probability is immediately 1.0.

If n >= k + maxPts - 1, then every possible stopping score is valid, meaning the answer is also 1.0.

The DP array stores the probability of reaching every exact score. The sliding window maintains the sum of probabilities that can transition into the current score.

For each score:

dp[score] = window_sum / maxPts

This computes the probability of landing exactly on that score.

If the score is still below k, Alice may continue drawing, so this probability contributes to future transitions by being added into the window.

Otherwise, the score is terminal and contributes directly to the final answer.

Finally, the oldest value is removed from the sliding window once it moves outside the valid transition range.

Go Solution

func new21Game(n int, k int, maxPts int) float64 {
    if k == 0 || n >= k+maxPts-1 {
        return 1.0
    }

    dp := make([]float64, n+1)
    dp[0] = 1.0

    windowSum := 1.0
    result := 0.0

    for score := 1; score <= n; score++ {
        dp[score] = windowSum / float64(maxPts)

        if score < k {
            windowSum += dp[score]
        } else {
            result += dp[score]
        }

        if score >= maxPts {
            windowSum -= dp[score-maxPts]
        }
    }

    return result
}

The Go implementation follows the same logic as the Python version.

The primary difference is explicit type conversion:

float64(maxPts)

because Go does not automatically convert integers to floating-point values.

The DP array is implemented using a slice of float64. Since all probabilities are decimal values, floating-point arithmetic is necessary throughout the solution.

Worked Examples

Example 1

Input: n = 10, k = 1, maxPts = 10

Alice stops after exactly one draw.

Score dp[score] Final?
1 0.1 Yes
2 0.1 Yes
3 0.1 Yes
4 0.1 Yes
5 0.1 Yes
6 0.1 Yes
7 0.1 Yes
8 0.1 Yes
9 0.1 Yes
10 0.1 Yes

All stopping scores are at most 10.

Final probability:

$$1.0$$

Example 2

Input: n = 6, k = 1, maxPts = 10

Again, Alice stops after one draw.

Valid stopping scores:

  • 1 through 6

Invalid scores:

  • 7 through 10
Score Probability
1 0.1
2 0.1
3 0.1
4 0.1
5 0.1
6 0.1

Total:

$$0.6$$

Example 3

Input: n = 21, k = 17, maxPts = 10

The DP evolves gradually.

Initial state:

Variable Value
dp[0] 1.0
windowSum 1.0

For score 1:

$$dp[1] = 1.0 / 10 = 0.1$$

Since 1 < 17, add to window.

Variable Value
windowSum 1.1

For score 2:

$$dp[2] = 1.1 / 10 = 0.11$$

Continue similarly.

Once scores reach 17 or higher, probabilities contribute directly to the final answer instead of extending the window.

The final accumulated probability becomes:

$$0.73278$$

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each score is processed exactly once
Space O(n) DP array stores probabilities for scores 0 through n

The sliding window optimization is what reduces the time complexity from quadratic to linear. Every DP state enters and leaves the window exactly once, so the total work is proportional to n.

Test Cases

sol = Solution()

assert abs(sol.new21Game(10, 1, 10) - 1.0) < 1e-5  # Example 1
assert abs(sol.new21Game(6, 1, 10) - 0.6) < 1e-5   # Example 2
assert abs(sol.new21Game(21, 17, 10) - 0.73278) < 1e-5  # Example 3

assert abs(sol.new21Game(0, 0, 1) - 1.0) < 1e-5   # No draws needed
assert abs(sol.new21Game(1, 0, 10) - 1.0) < 1e-5  # k == 0 edge case
assert abs(sol.new21Game(10000, 10000, 1) - 1.0) < 1e-5  # Deterministic draws
assert abs(sol.new21Game(5, 10, 1) - 0.0) < 1e-5  # Impossible to stop within n
assert abs(sol.new21Game(20, 10, 10) - 1.0) < 1e-5  # All stopping scores valid
assert abs(sol.new21Game(18, 17, 10) - 0.285714) < 1e-5  # Partial probability range

Test Summary

Test Why
(10, 1, 10) Basic single-draw example
(6, 1, 10) Partial valid outcomes
(21, 17, 10) Standard complex case
(0, 0, 1) Immediate termination
(1, 0, 10) k == 0 edge case
(10000, 10000, 1) Large deterministic case
(5, 10, 1) Impossible success scenario
(20, 10, 10) All final scores valid
(18, 17, 10) Mixed valid and invalid stopping scores

Edge Cases

One important edge case occurs when k == 0. In this situation, Alice never draws any cards because she already satisfies the stopping condition. Her score remains 0, which is always less than or equal to n. A common bug is continuing into the DP logic and producing incorrect probabilities. The implementation handles this immediately with an early return of 1.0.

Another tricky case occurs when n >= k + maxPts - 1. The largest possible stopping score is k + maxPts - 1, because the final draw adds at most maxPts. If n is at least this large, then every possible final score is valid. Without this optimization, the DP still works, but unnecessary computation occurs. The implementation returns 1.0 immediately.

A subtle edge case involves removing outdated probabilities from the sliding window. If the removal index is off by one, probabilities may remain in the window too long or disappear too early, causing incorrect averages. The implementation carefully removes:

dp[score - maxPts]

exactly when:

score >= maxPts

which preserves the correct transition range at every iteration.