Dice Roll Simulation

Hard

#1142Time: O(n * faces). This is a significant improvement as we removed the dependency on `max_rollMax` from the loops.Space: O(n * faces). We use a 2D DP table of size `(n+1) x 6` and a sum array of size `n+1`.1 company

Patterns

Dynamic Programming

Data structures

Array

Companies

Akuna Capital

Prompt

A die simulator generates a random number from 1 to 6 for each roll. You introduced a constraint to the generator such that it cannot roll the number i more than rollMax[i] (1-indexed) consecutive times.

Given an array of integers rollMax and an integer n, return the number of distinct sequences that can be obtained with exact n rolls. Since the answer may be too large, return it modulo 10⁹ + 7.

Two sequences are considered different if at least one element differs from each other.

Example 1:

Input: n = 2, rollMax = [1,1,2,2,2,3]
Output: 34
Explanation: There will be 2 rolls of die, if there are no constraints on the die, there are 6 * 6 = 36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 = 34.

Example 2:

Input: n = 2, rollMax = [1,1,1,1,1,1]
Output: 30

Example 3:

Input: n = 3, rollMax = [1,1,1,2,2,3]
Output: 181

Constraints:

1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15

Approaches

4 approaches with complexity analysis and trade-offs.

This is a more efficient approach that redefines the DP state to reduce the dimensions of the table and improve the time complexity. Instead of tracking the consecutive count explicitly in the state, we calculate the number of valid sequences by taking the total possible sequences and subtracting the invalid ones. This 'subtraction' principle leads to a faster solution.

Algorithm

Define dp[i][j] as the number of valid sequences of length i ending with face j.
Define S[i] as the total number of valid sequences of length i, which is sum(dp[i][p]) over all faces p.
Base case: S[0] = 1 (for the empty sequence).
Iterate i from 1 to n:
- For each face j from 0 to 5:
  - Start with dp[i][j] = S[i-1], which is the count if there were no constraints.
  - Let k = rollMax[j]. We must subtract the invalid sequences that end with more than k consecutive j's.
  - If i > k, the number of invalid sequences is the number of valid sequences of length i-k-1 that did not end in j. This is S[i-k-1] - dp[i-k-1][j]. Subtract this from dp[i][j].
  - If i == k, there is exactly one invalid sequence (all j's). Subtract 1.
- Calculate S[i] by summing dp[i][j] over all j.
Return S[n].

Walkthrough

Let dp[i][j] be the number of valid sequences of length i ending with face j. Let S[i] be the total number of valid sequences of length i.

To calculate dp[i][j], we can start with the total number of ways to form a sequence of length i-1 (S[i-1]) and append j. This gives us S[i-1] potential sequences.

However, this includes invalid sequences where j is rolled more than rollMax[j] consecutive times. We must subtract these. An invalid sequence of length i ending with rollMax[j] + 1 consecutive j's must have the form ... p j j ... j, where p != j. The prefix ... p has length i - (rollMax[j] + 1). The number of such prefixes is the number of valid sequences of that length that do not end in j, which is S[i - rollMax[j] - 1] - dp[i - rollMax[j] - 1][j]. This gives us our recurrence.

1class Solution {2    public int dieSimulator(int n, int[] rollMax) {3        long MOD = 1_000_000_007;4        long[][] dp = new long[n + 1][6];5        long[] sum = new long[n + 1];6        sum[0] = 1;7 8        for (int i = 1; i <= n; i++) {9            long currentSum = 0;10            for (int j = 0; j < 6; j++) {11                // Initially, assume we can append j to any valid sequence of length i-112                dp[i][j] = sum[i - 1];13                14                int k = rollMax[j];15                if (i > k) {16                    // Subtract sequences of length i-k-1 not ending with j17                    long toSubtract = (sum[i - k - 1] - dp[i - k - 1][j] + MOD) % MOD;18                    dp[i][j] = (dp[i][j] - toSubtract + MOD) % MOD;19                } else if (i == k) {20                    // Subtract the sequence of all j's21                    dp[i][j] = (dp[i][j] - 1 + MOD) % MOD;22                }23                currentSum = (currentSum + dp[i][j]) % MOD;24            }25            sum[i] = currentSum;26        }27 28        return (int) sum[n];29    }30}

Complexity

Time

O(n * faces). This is a significant improvement as we removed the dependency on `max_rollMax` from the loops.

Space

O(n * faces). We use a 2D DP table of size `(n+1) x 6` and a sum array of size `n+1`.

Trade-offs

Pros

Much faster time complexity than the 3D DP approaches.
The DP state is simpler (2D vs 3D).

Cons

Still uses linear space with respect to n.
The recurrence relation is slightly more complex to derive.

This approach uses a three-dimensional dynamic programming table to solve the problem. The state dp[i][j][k] represents the number of valid sequences of length i that end with exactly k consecutive rolls of the number j+1. We build this table up from i=1 to n, calculating the number of possibilities at each step based on the results of the previous step.

Algorithm

Define a 3D DP state dp[i][j][k] as the number of distinct sequences of length i rolls, where the last roll is face j (0-indexed), and it's the k-th consecutive occurrence of j.
Initialize a 3D array dp[n+1][6][16] to store these values.
Base Case: For i = 1, we can roll any face j once. So, dp[1][j][1] = 1 for all j from 0 to 5.
Transitions: Iterate from i = 2 to n. For each face j:
- To form a sequence ending with k > 1 consecutive j's, we must append a j to a sequence of length i-1 that ended with k-1 consecutive j's. Thus, dp[i][j][k] = dp[i-1][j][k-1].
- To form a sequence ending with k = 1 consecutive j's, we must append a j to any valid sequence of length i-1 that ended with a face other than j. This can be calculated as total_sequences[i-1] - sequences_ending_with_j[i-1].
To optimize, we maintain an array total[i] storing the total number of valid sequences of length i.
The final answer is the sum of dp[n][j][k] over all possible j and k, which is total[n].

Walkthrough

In this method, we define a DP state dp[i][j][k] as the number of distinct sequences of length i rolls, where the last roll is face j (0-indexed), and it's the k-th consecutive occurrence of j.

The state transitions are as follows:

To form a sequence of length i ending with k > 1 consecutive j's, we must append a j to a sequence of length i-1 that ended with k-1 consecutive j's. Thus, dp[i][j][k] = dp[i-1][j][k-1].
To form a sequence of length i ending with k = 1 consecutive j's, we must append a j to a sequence of length i-1 that ended with any face other than j. The number of such sequences is the total number of valid sequences of length i-1 minus the number of sequences of length i-1 ending in j.

We can optimize the calculation for the k=1 case by pre-calculating the total number of sequences for length i-1. The final answer is the sum of dp[n][j][k] over all possible j and k.

1class Solution {2    public int dieSimulator(int n, int[] rollMax) {3        long MOD = 1_000_000_007;4        // dp[i][j][k]: number of sequences of length i ending with k consecutive j's5        long[][][] dp = new long[n + 1][6][16];6        long[] total = new long[n + 1];7 8        // Base case: i = 19        for (int j = 0; j < 6; j++) {10            dp[1][j][1] = 1;11        }12        total[1] = 6;13 14        for (int i = 2; i <= n; i++) {15            long currentTotal = 0;16            for (int j = 0; j < 6; j++) { // current face17                long sumEndingWithJPrev = 0;18                for (int k = 1; k <= rollMax[j]; k++) {19                    sumEndingWithJPrev = (sumEndingWithJPrev + dp[i - 1][j][k]) % MOD;20                }21 22                // Case 1: current roll j is the first in a consecutive sequence23                dp[i][j][1] = (total[i - 1] - sumEndingWithJPrev + MOD) % MOD;24 25                // Case 2: current roll j extends a consecutive sequence26                for (int k = 2; k <= rollMax[j]; k++) {27                    dp[i][j][k] = dp[i - 1][j][k - 1];28                }29                30                long sumEndingWithJCurr = 0;31                for (int k = 1; k <= rollMax[j]; k++) {32                    sumEndingWithJCurr = (sumEndingWithJCurr + dp[i][j][k]) % MOD;33                }34                currentTotal = (currentTotal + sumEndingWithJCurr) % MOD;35            }36            total[i] = currentTotal;37        }38 39        return (int) total[n];40    }41}

Complexity

Time

O(n * faces * max_rollMax). The loops iterate up to `n`, 6 (faces), and `max_rollMax` (at most 15).

Space

O(n * faces * max_rollMax). We use a 3D array of size `(n+1) x 6 x 16`.

Trade-offs

Pros

Conceptually straightforward application of dynamic programming.
Easy to understand the state transitions.

Cons

High space complexity, which can be an issue for larger n.
The time complexity is higher than more optimized approaches.

This approach improves upon the 3D DP solution by reducing its space complexity. Since the calculation for dp[i] only depends on the results from dp[i-1], we don't need to store the entire DP table. We can use only two layers of the DP table: one for the current state i and one for the previous state i-1, effectively reducing the space complexity from linear to constant with respect to n.

Algorithm

The logic and state transitions are identical to the previous 3D DP approach.
Instead of a dp[n+1][...][...] table, we use two tables, dp[6][16] and prev_dp[6][16].
Initialize prev_dp for the base case i=1.
In each iteration i from 2 to n, we calculate the dp table (for state i) using the values from the prev_dp table (for state i-1).
After computing the values for the current iteration, we copy the dp table to prev_dp to prepare for the next iteration.
This reduces the space from being proportional to n to being constant (with respect to n).

Walkthrough

The core logic remains the same as the basic 3D DP approach. The key difference is memory management. We observe that to compute the number of sequences for i rolls, we only need the results from i-1 rolls. Therefore, storing the entire history for 1...i-2 is unnecessary.

We use two 2D arrays, prev_dp to hold the results for i-1 rolls and dp to compute the results for i rolls. After each iteration i, the contents of dp become the prev_dp for the next iteration i+1.

1class Solution {2    public int dieSimulator(int n, int[] rollMax) {3        long MOD = 1_000_000_007;4        long[][] prev_dp = new long[6][16];5        long total_prev = 0;6 7        // Base case: i = 18        for (int j = 0; j < 6; j++) {9            prev_dp[j][1] = 1;10        }11        total_prev = 6;12        13        if (n == 1) return (int) total_prev;14 15        for (int i = 2; i <= n; i++) {16            long[][] dp = new long[6][16];17            long total_curr = 0;18            for (int j = 0; j < 6; j++) {19                long sumEndingWithJPrev = 0;20                for (int k = 1; k <= rollMax[j]; k++) {21                    sumEndingWithJPrev = (sumEndingWithJPrev + prev_dp[j][k]) % MOD;22                }23 24                dp[j][1] = (total_prev - sumEndingWithJPrev + MOD) % MOD;25 26                for (int k = 2; k <= rollMax[j]; k++) {27                    dp[j][k] = prev_dp[j][k - 1];28                }29                30                long sumEndingWithJCurr = 0;31                for (int k = 1; k <= rollMax[j]; k++) {32                    sumEndingWithJCurr = (sumEndingWithJCurr + dp[j][k]) % MOD;33                }34                total_curr = (total_curr + sumEndingWithJCurr) % MOD;35            }36            prev_dp = dp;37            total_prev = total_curr;38        }39 40        return (int) total_prev;41    }42}

Complexity

Time

O(n * faces * max_rollMax). The time complexity remains the same as the previous approach.

Space

O(faces * max_rollMax). The space is now constant with respect to `n`, which is a significant improvement.

Trade-offs

Pros

Greatly reduced space complexity compared to the basic 3D DP.
Makes the solution feasible for much larger n if memory were the only constraint.

Cons

Time complexity is still not optimal.
Involves managing two tables and copying data between them in each iteration.

This is the most efficient approach, building upon the 2D DP with subtraction method. It optimizes the space complexity to be constant by noticing that we only need to remember a fixed number of previous states to calculate the current state. By using circular arrays, we can discard old, unnecessary information and keep the memory footprint small and constant, regardless of n.

Algorithm

The logic is identical to the 2D DP with Subtraction approach.
Observe that dp[i] depends on dp[i-1] and dp[i - k - 1], where k is rollMax[j].
The maximum look-back required is max(rollMax) + 1. Since max(rollMax) is at most 15, we only need to store the last ~16 states.
We use circular arrays for dp and sum tables to store only this recent history. The size of these circular arrays would be max(rollMax) + 2.
We use the modulo operator on the current roll index i to map it to an index in our small circular arrays (e.g., dp[i % buffer_size][j]).
This reduces the space complexity from O(n * faces) to O(max_rollMax * faces), which is constant.

Walkthrough

This approach refines the 2D DP with Subtraction method by optimizing its space usage. The recurrence relation dp[i][j] depends on values from dp[i-1] and dp[i - rollMax[j] - 1]. The maximum look-back required is determined by the largest value in rollMax, which is at most 15. This means we only need to store the results for the last 16 or so steps.

We can implement this using circular arrays for our dp and sum tables. A circular array of a fixed size (e.g., 17, which is max(rollMax) + 2) is sufficient. We use the modulo operator on the current roll index i to map it to an index in our small arrays. For example, the state for roll i is stored at index i % 17. This clever trick reduces the space complexity from O(n * faces) to O(max_rollMax * faces), which is constant.

1class Solution {2    public int dieSimulator(int n, int[] rollMax) {3        long MOD = 1_000_000_007;4        // We only need to store the last 16 states (max(rollMax) + 1)5        // Use a buffer of size 17 for safety with modulo arithmetic6        int bufferSize = 17; 7        long[][] dp = new long[bufferSize][6];8        long[] sum = new long[bufferSize];9        sum[0] = 1;10 11        for (int i = 1; i <= n; i++) {12            int i_mod = i % bufferSize;13            int i_minus_1_mod = (i - 1 + bufferSize) % bufferSize;14            long currentSum = 0;15 16            for (int j = 0; j < 6; j++) {17                dp[i_mod][j] = sum[i_minus_1_mod];18                19                int k = rollMax[j];20                if (i > k) {21                    int i_minus_k_minus_1_mod = (i - k - 1 + bufferSize) % bufferSize;22                    long toSubtract = (sum[i_minus_k_minus_1_mod] - dp[i_minus_k_minus_1_mod][j] + MOD) % MOD;23                    dp[i_mod][j] = (dp[i_mod][j] - toSubtract + MOD) % MOD;24                } else if (i == k) {25                    dp[i_mod][j] = (dp[i_mod][j] - 1 + MOD) % MOD;26                }27                currentSum = (currentSum + dp[i_mod][j]) % MOD;28            }29            sum[i_mod] = currentSum;30        }31 32        return (int) sum[n % bufferSize];33    }34}

Complexity

Time

O(n * faces). The time complexity is the same as the previous approach and is optimal.

Space

O(max_rollMax * faces). This is constant space as it does not depend on `n`.

Trade-offs

Pros

Optimal time complexity.
Optimal constant space complexity.

Cons

The logic with circular arrays and modulo arithmetic can be slightly more complex to implement correctly.

Solutions

Solution

1class Solution {2private3  Integer[][][] f;4private5  int[] rollMax;6public7  int dieSimulator(int n, int[] rollMax) {8    f = new Integer[n][7][16];9    this.rollMax = rollMax;10    return dfs(0, 0, 0);11  }12private13  int dfs(int i, int j, int x) {14    if (i >= f.length) {15      return 1;16    }17    if (f[i][j][x] != null) {18      return f[i][j][x];19    }20    long ans = 0;21    for (int k = 1; k <= 6; ++k) {22      if (k != j) {23        ans += dfs(i + 1, k, 1);24      } else if (x < rollMax[j - 1]) {25        ans += dfs(i + 1, j, x + 1);26      }27    }28    ans %= 1000000007;29    return f[i][j][x] = (int)ans;30  }31}

1class Solution {2public:3  int dieSimulator(int n, vector<int> &rollMax) {4    int f[n][7][16];5    memset(f, 0, sizeof f);6    const int mod = 1e9 + 7;7    function<int(int, int, int)> dfs = [&](int i, int j, int x) -> int {8      if (i >= n) {9        return 1;10      }11      if (f[i][j][x]) {12        return f[i][j][x];13      }14      long ans = 0;15      for (int k = 1; k <= 6; ++k) {16        if (k != j) {17          ans += dfs(i + 1, k, 1);18        } else if (x < rollMax[j - 1]) {19          ans += dfs(i + 1, j, x + 1);20        }21      }22      ans %= mod;23      return f[i][j][x] = ans;24    };25    return dfs(0, 0, 0);26  }27};

1class Solution:2    def dieSimulator(self, n: int, rollMax: List[int]) -> int: @ cache def dfs(i, j, x): if i >= n: return 1 ans = 0 for k in range(1, 7): if k != j: ans += dfs(i + 1, k, 1) elif x < rollMax[j - 1]: ans += dfs(i + 1, j, x + 1) return ans % (10 ** 9 + 7) return dfs(0, 0, 0)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  Integer[][][] f;4private5  int[] rollMax;6public7  int dieSimulator(int n, int[] rollMax) {8    f = new Integer[n][7][16];9    this.rollMax = rollMax;10    return dfs(0, 0, 0);11  }12private13  int dfs(int i, int j, int x) {14    if (i >= f.length) {15      return 1;16    }17    if (f[i][j][x] != null) {18      return f[i][j][x];19    }20    long ans = 0;21    for (int k = 1; k <= 6; ++k) {22      if (k != j) {23        ans += dfs(i + 1, k, 1);24      } else if (x < rollMax[j - 1]) {25        ans += dfs(i + 1, j, x + 1);26      }27    }28    ans %= 1000000007;29    return f[i][j][x] = (int)ans;30  }31}

1class Solution {2public:3  int dieSimulator(int n, vector<int> &rollMax) {4    int f[n][7][16];5    memset(f, 0, sizeof f);6    const int mod = 1e9 + 7;7    function<int(int, int, int)> dfs = [&](int i, int j, int x) -> int {8      if (i >= n) {9        return 1;10      }11      if (f[i][j][x]) {12        return f[i][j][x];13      }14      long ans = 0;15      for (int k = 1; k <= 6; ++k) {16        if (k != j) {17          ans += dfs(i + 1, k, 1);18        } else if (x < rollMax[j - 1]) {19          ans += dfs(i + 1, j, x + 1);20        }21      }22      ans %= mod;23      return f[i][j][x] = ans;24    };25    return dfs(0, 0, 0);26  }27};

1class Solution:2    def dieSimulator(self, n: int, rollMax: List[int]) -> int: @ cache def dfs(i, j, x): if i >= n: return 1 ans = 0 for k in range(1, 7): if k != j: ans += dfs(i + 1, k, 1) elif x < rollMax[j - 1]: ans += dfs(i + 1, j, x + 1) return ans % (10 ** 9 + 7) return dfs(0, 0, 0)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.