LeetCode 1223 - Dice Roll Simulation

The problem asks us to calculate the total number of valid sequences generated by rolling a six-sided die n times, with the added constraint that each face i cannot appear more than rollMax[i] consecutive times.

leetcodehardarraydynamic-programming

LeetCode Problem 1223

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to calculate the total number of valid sequences generated by rolling a six-sided die n times, with the added constraint that each face i cannot appear more than rollMax[i] consecutive times. Here, rollMax is a 6-element array corresponding to the maximum allowed consecutive appearances for each die face from 1 to 6. The result should be returned modulo 10^9 + 7 due to potential large numbers.

In other words, if we roll the die n times, we want to count all sequences of length n where the constraints from rollMax are satisfied. The input n can be as large as 5000, and each rollMax[i] is at most 15. This implies that a brute-force enumeration of all sequences is computationally infeasible because the number of possible sequences grows exponentially (6^n).

Important edge cases include scenarios where rollMax is all 1s (sequences with immediate repetition are disallowed) or when n is small (like 1 or 2), which can be solved almost trivially. The constraints guarantee that rollMax is always valid (positive integers) and the array always has exactly 6 elements, so we do not need to handle malformed input.

Approaches

The brute-force approach would be to generate all 6^n sequences recursively or iteratively and check each sequence against the rollMax constraints. While this produces the correct result, it is completely impractical for n = 5000 because of exponential growth in both time and memory.

The dynamic programming approach is the key observation. We notice that at any step, the number of valid sequences depends on the last number rolled and how many times it has consecutively appeared. Thus, we can define a DP state dp[i][j][k], where i is the current roll index, j is the last die face rolled, and k is the number of consecutive times j has been rolled. Using this state, we can incrementally build solutions by considering all valid previous states. By carefully updating the DP array and using modulo arithmetic, we can efficiently compute the total count for n rolls without enumerating all sequences.

Approach Time Complexity Space Complexity Notes
Brute Force O(6^n) O(n) Enumerates all sequences and checks validity
Dynamic Programming O(n * 6 * max(rollMax)) O(n * 6 * max(rollMax)) Uses DP over rolls, last number, and consecutive count to compute valid sequences

Algorithm Walkthrough

  1. Initialize a 2D DP array dp[j][k] where j represents the die face (0-5) and k represents consecutive occurrences of j. dp[j][k] stores the number of sequences of the current length ending with face j appearing consecutively k times.
  2. Set the base case for the first roll: each face j can appear once, so dp[j][1] = 1 for all j.
  3. Iterate from roll 2 to n. For each new roll, create a new DP array new_dp to store updated counts.
  4. For each die face j, consider all possible consecutive counts k (from 1 to rollMax[j]).
  5. For each possible previous die face i, if i == j, we can only extend sequences ending with i if the consecutive count k - 1 is valid. Otherwise, if i != j, we can start a new sequence with j by summing all sequences ending with i regardless of their consecutive count.
  6. Update new_dp[j][k] with the calculated counts modulo 10^9 + 7.
  7. After processing all faces for this roll, replace dp with new_dp.
  8. After all n rolls, sum over all dp[j][k] to get the total number of valid sequences.

Why it works: The DP approach guarantees correctness because it tracks all necessary state: the last face rolled and how many times it has appeared consecutively. This ensures that no sequence violates the rollMax constraints and all valid sequences are counted exactly once.

Python Solution

from typing import List

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10**9 + 7
        max_roll = max(rollMax)
        dp = [[0] * (max_roll + 1) for _ in range(6)]
        
        for j in range(6):
            dp[j][1] = 1
        
        for roll in range(1, n):
            new_dp = [[0] * (max_roll + 1) for _ in range(6)]
            for j in range(6):
                for k in range(1, rollMax[j] + 1):
                    if k == 1:
                        new_dp[j][k] = sum(dp[i][c] for i in range(6) if i != j for c in range(1, rollMax[i] + 1)) % MOD
                    else:
                        new_dp[j][k] = dp[j][k - 1]
            dp = new_dp
        
        return sum(dp[j][k] for j in range(6) for k in range(1, rollMax[j] + 1)) % MOD

The Python solution initializes a DP array with dimensions [6][max_roll+1] to store counts. The first roll is seeded with 1 for each face. For subsequent rolls, a new DP array is created to hold updated counts. Sequences are extended either by incrementing the consecutive count for the same face or by starting a new count for a different face. The modulo operation ensures no integer overflow. Finally, the sum over all states yields the total number of valid sequences.

Go Solution

func dieSimulator(n int, rollMax []int) int {
    const MOD = 1e9 + 7
    maxRoll := 0
    for _, v := range rollMax {
        if v > maxRoll {
            maxRoll = v
        }
    }
    dp := make([][]int, 6)
    for i := 0; i < 6; i++ {
        dp[i] = make([]int, maxRoll+1)
        dp[i][1] = 1
    }

    for roll := 1; roll < n; roll++ {
        newDp := make([][]int, 6)
        for i := 0; i < 6; i++ {
            newDp[i] = make([]int, maxRoll+1)
        }
        for j := 0; j < 6; j++ {
            for k := 1; k <= rollMax[j]; k++ {
                if k == 1 {
                    sum := 0
                    for i := 0; i < 6; i++ {
                        if i == j {
                            continue
                        }
                        for c := 1; c <= rollMax[i]; c++ {
                            sum = (sum + dp[i][c]) % MOD
                        }
                    }
                    newDp[j][k] = sum
                } else {
                    newDp[j][k] = dp[j][k-1]
                }
            }
        }
        dp = newDp
    }

    result := 0
    for j := 0; j < 6; j++ {
        for k := 1; k <= rollMax[j]; k++ {
            result = (result + dp[j][k]) % MOD
        }
    }
    return result
}

In Go, slices are used for the DP array. Initialization and updating follow the same logic as in Python. Go-specific considerations include explicit slice creation and modulo arithmetic to prevent overflow.

Worked Examples

Example 1: n=2, rollMax=[1,1,2,2,2,3]

  1. First roll: dp[j][1] = 1 for all j.
  2. Second roll: compute new_dp. Faces 1 and 2 cannot appear consecutively (k=2 not allowed), so only sequences where j != previous are counted.
  3. Total valid sequences = 34.

Example 2: n=2, rollMax=[1,1,1,1,1,1]

  1. First roll: each face once.
  2. Second roll: consecutive repeats disallowed, only sequences with different faces counted.
  3. Total = 30.

Example 3: n=3, rollMax=[1,1,1,2,2,3]

  1. Iterate rolls, updating DP for consecutive constraints.
  2. Sequences extending previous faces respect max consecutive counts.
  3. Total = 181.

Complexity Analysis

Measure Complexity Explanation
Time O(n * 6 * max(rollMax)) For each roll, we iterate over 6 faces and at most rollMax[i] consecutive counts
Space O(6 * max(rollMax)) Only two DP arrays of size 6 * maxRoll are stored at any time

Because `max