Dice Roll Simulation solution and explanation
Google
9 more videos on this problem
LeetCode 1223. Dice Roll SimulationHappy Coding · 28:08 · 5K views
1223 Dice Roll SimulationKelvin Chandra · 4:41 · 4K views
花花酱 LeetCode 1223 Dice Roll Simulation - 刷题找工作 EP275Hua Hua · 26:26 · 3K views
Dice Roll Simulation || LeetCode 1223 || Dynamic programming top-down Memoization solutionInterviewDose · 1:06 · 1K views
LeetCode 1223 - Dice Roll Simulation - PythonAlpha-Code · 10:51 · 452 views
Leetcode 1223. Dice Roll Simulation (linear dp)LetsCode · 9:04 · 397 views
Leetcode 1223. Dice Roll SimulationFearless Learner · 11:35 · 320 views
1223. Dice Roll SimulationAlgorithms for Big Bucks · 11:17 · 125 views
LeetCode 1223: Dice Roll SimulationAlitaCode · 28:43 · 37 views
No Sound Leetcode 1223: Dice Roll SimulationExtremeProgrammer · 2:56 · 23 views
The problem
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 109 + 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 <= 5000rollMax.length == 61 <= rollMax[i] <= 15
Approach overview
Problem Overview: You roll a 6-sided dice n times, but each face has a limit on how many times it can appear consecutively. The array rollMax[6] defines that limit for each face. The goal is to count how many valid sequences of length n exist without violating those consecutive constraints.
Approach 1: Dynamic Programming with 3D Array (Time: O(n * 6 * maxRoll), Space: O(n * 6 * maxRoll))
This approach tracks three pieces of state: the roll index, the face value, and the current streak length of that face. Define dp[i][j][k] as the number of ways to reach roll i where the last face is j and it has appeared k consecutive times. For every new roll, iterate over all previous faces. If the same face appears again, increase the streak only if k + 1 ≤ rollMax[j]. If a different face appears, reset the streak to 1. This explicitly models every valid state and ensures constraints are respected at each step. It’s straightforward to implement and useful for understanding state transitions in dynamic programming.
Approach 2: Dynamic Programming with 2D Array (Time: O(n * 6), Space: O(n * 6))
The 3D state can be compressed by tracking only the total sequences ending with each face. Let dp[i][j] represent the number of sequences of length i ending with face j. Normally you would extend from the total sequences of length i-1, but you must subtract sequences that would violate the rollMax constraint. When the streak of face j would exceed its limit, remove those invalid contributions using previously computed states. This converts the explicit streak dimension into arithmetic on previous totals. The result is significantly fewer states while still enforcing the constraints.
This optimization is common in dynamic programming problems where a dimension can be inferred from earlier values. The dice faces themselves are stored in a simple array, and transitions iterate over the six possible outcomes each step.
Recommended for interviews: Start by describing the 3D DP state because it clearly models the constraints and shows you understand the problem structure. Then mention the 2D optimization that removes the streak dimension. Interviewers typically expect the optimized dynamic programming approach since it reduces memory and keeps the time complexity near linear in n.
Approach 1: Dynamic Programming with 3D Array
In this approach, we'll use a 3D dynamic programming (DP) array to keep track of the number of ways to have a valid sequence up to the ith roll, ending with j as the last rolled number, with k consecutive rolls of j.
Our main DP state can be expressed as dp[i][j][k], where i represents the number of rolls, j represents the last face value, and k represents how many times this face value has been rolled consecutively.
For the transition, notice that if we want the current roll to be number j, we can extend a sequence ending with j k times using the face j again if k < rollMax[j-1]. If we use a different number instead, we reset k to 1 for a new number.
MOD = 10**9 + 7
class Solution:
def dieSimulator(self, n: int, rollMax: List[int]) -> int:
dp = [[[0] * 16 for _ in range(6)] for _ in range(n+1)]
for j in range(6):
dp[1][j][1] = 1
for i in range(2, n+1):
for j in range(6):
for k in range(6):
if k != j:
for x in range(1, rollMax[k] + 1):
dp[i][j][1] = (dp[i][j][1] + dp[i-1][k][x]) % MOD
for x in range(1, rollMax[j]):
dp[i][j][x+1] = (dp[i][j][x+1] + dp[i-1][j][x]) % MOD
return sum(dp[n][j][x] for j in range(6) for x in range(1, rollMax[j]+1)) % MODconst MOD = 1000000007;
function dieSimulator(n, rollMax) {
const dp = Array.from({ length: n + 1 }, () => Array.from({ length: 6 }, () => Array(16).fill(0)));
for (let j = 0; j < 6; ++j) dp[1][j][1] = 1;
for (let i = 2; i <= n; ++i) {
for (let j = 0; j < 6; ++j) {
for (let k = 0; k < 6; ++k) {
if (k !== j) {
for (let x = 1; x <= rollMax[k]; ++x) {
dp[i][j][1] = (dp[i][j][1] + dp[i - 1][k][x]) % MOD;
}
}
}
for (let x = 1; x < rollMax[j]; ++x) {
dp[i][j][x + 1] = (dp[i][j][x + 1] + dp[i - 1][j][x]) % MOD;
}
}
}
let result = 0;
for (let j = 0; j < 6; ++j) {
for (let x = 1; x <= rollMax[j]; ++x) {
result = (result + dp[n][j][x]) % MOD;
}
}
return result;
}This Python solution uses a 3D DP array to keep track of valid rolls, as discussed. The final result is computed by summing up all valid sequences of length n for any face and consecutive counts allowed by rollMax.
Time Complexity: O(n * 6 * 6 * m) where m = max(rollMax)
Space Complexity: O(n * 6 * m)
Approach 2: Dynamic Programming with 2D Array
Instead of a 3D array, this approach uses a 2D array, where dp[i][j] represents the number of sequences of length i that end with number j, without specifically tracking consecutive count. This approach is less memory intensive but requires careful bookkeeping of the last rolled sequences according to constraints.
class Solution {
private static final int MOD = 1000000007;
public int dieSimulator(int n, int[] rollMax) {
int[][] dp = new int[n + 1][6];
int[] sumDp = new int[n + 1];
Arrays.fill(dp[1], 1);
sumDp[1] = 6;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 6; j++) {
dp[i][j] = sumDp[i - 1];
if (i - rollMax[j] == 1) {
dp[i][j] = (dp[i][j] - 1 + MOD) % MOD;
} else if (i - rollMax[j] > 1) {
int subtract = 0;
for (int k = 0; k < 6; k++) {
if (k == j) continue;
subtract = (subtract + dp[i - rollMax[j] - 1][k]) % MOD;
}
dp[i][j] = (dp[i][j] - subtract + MOD) % MOD;
}
}
sumDp[i] = 0;
for (int j = 0; j < 6; j++) {
sumDp[i] = (sumDp[i] + dp[i][j]) % MOD;
}
}
return sumDp[n];
}
}public class Solution {
const int MOD = 1000000007;
public int DieSimulator(int n, int[] rollMax) {
int[,] dp = new int[n + 1, 6];
int[] sumDp = new int[n + 1];
for (int j = 0; j < 6; ++j) dp[1, j] = 1;
sumDp[1] = 6;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < 6; ++j) {
dp[i, j] = sumDp[i - 1];
if (i == rollMax[j] + 1) {
dp[i, j] = (dp[i, j] - 1 + MOD) % MOD;
} else if (i > rollMax[j] + 1) {
for (int k = 0; k < 6; ++k) {
if (k != j) {
dp[i, j] = (dp[i, j] - dp[i - rollMax[j] - 1, k] + MOD) % MOD;
}
}
}
}
sumDp[i] = 0;
for (int j = 0; j < 6; ++j) {
sumDp[i] = (sumDp[i] + dp[i, j]) % MOD;
}
}
return sumDp[n];
}
}This Java solution employs a 2D DP array to find valid sequences. With each roll, it updates the sum of possibilities by calculating across different faces.
Time Complexity: O(n * 6 * 6)
Space Complexity: O(n * 6)
Approach 3: Memoization Search
We can design a function dfs(i, j, x) to represent the number of schemes starting from the i-th dice roll, with the current dice roll being j, and the number of consecutive times j is rolled being x. The range of j is [1, 6], and the range of x is [1, rollMax[j - 1]]. The answer is dfs(0, 0, 0).
The calculation process of the function dfs(i, j, x) is as follows:
- If
i \ge n, it means thatndice have been rolled, return1. - Otherwise, we enumerate the number
krolled next time. Ifk \ne j, we can directly rollk, and the number of consecutive timesjis rolled will be reset to1, so the number of schemes isdfs(i + 1, k, 1). Ifk = j, we need to judge whetherxis less thanrollMax[j - 1]. If it is less, we can continue to rollj, and the number of consecutive timesjis rolled will increase by1, so the number of schemes isdfs(i + 1, j, x + 1). Finally, add all the scheme numbers to get the value ofdfs(i, j, x). Note that the answer may be very large, so we need to take the modulus of10^9 + 7.
During the process, we can use memoization search to avoid repeated calculations.
The time complexity is O(n times k^2 times M), and the space complexity is O(n times k times M). Here, k is the range of dice points, and M is the maximum number of times a certain point can be rolled consecutively.
class Solution {
public:
int dieSimulator(int n, vector<int>& rollMax) {
int f[n][7][16];
memset(f, 0, sizeof f);
const int mod = 1e9 + 7;
function<int(int, int, int)> dfs = [&](int i, int j, int x) -> int {
if (i >= n) {
return 1;
}
if (f[i][j][x]) {
return f[i][j][x];
}
long ans = 0;
for (int k = 1; k <= 6; ++k) {
if (k != j) {
ans += dfs(i + 1, k, 1);
} else if (x < rollMax[j - 1]) {
ans += dfs(i + 1, j, x + 1);
}
}
ans %= mod;
return f[i][j][x] = ans;
};
return dfs(0, 0, 0);
}
};func dieSimulator(n int, rollMax []int) int {
f := make([][7][16]int, n)
const mod = 1e9 + 7
var dfs func(i, j, x int) int
dfs = func(i, j, x int) int {
if i >= n {
return 1
}
if f[i][j][x] != 0 {
return f[i][j][x]
}
ans := 0
for k := 1; k <= 6; k++ {
if k != j {
ans += dfs(i+1, k, 1)
} else if x < rollMax[j-1] {
ans += dfs(i+1, j, x+1)
}
}
f[i][j][x] = ans % mod
return f[i][j][x]
}
return dfs(0, 0, 0)
}Approach 4: Dynamic Programming
We can change the memoization search in Solution 1 to dynamic programming.
Define f[i][j][x] as the number of schemes for the first i dice rolls, with the i-th dice roll being j, and the number of consecutive times j is rolled being x. Initially, f[1][j][1] = 1, where 1 leq j leq 6. The answer is:
$
sum_{j=1}^6 sum_{x=1}^{rollMax[j-1]} f[n][j][x]
We enumerate the last dice roll as j, and the number of consecutive times j is rolled as x. The current dice roll can be 1, 2, cdots, 6. If the current dice roll is k, there are two cases:
- If k neq j
, we can directly rollk, and the number of consecutive timesjis rolled will be reset to1. Therefore, the number of schemesf[i][k][1]will increase byf[i-1][j][x]. - If k = j
, we need to judge whetherx+1is less than or equal torollMax[j-1]. If it is less than or equal to, we can continue to rollj, and the number of consecutive timesjis rolled will increase by1. Therefore, the number of schemesf[i][j][x+1]will increase byf[i-1][j][x].
The final answer is the sum of all f[n][j][x].
The time complexity is O(n times k^2 times M), and the space complexity is O(n times k times M). Here, k is the range of dice points, and M$ is the maximum number of times a certain point can be rolled consecutively.
class Solution {
public:
int dieSimulator(int n, vector<int>& rollMax) {
int f[n + 1][7][16];
memset(f, 0, sizeof f);
for (int j = 1; j <= 6; ++j) {
f[1][j][1] = 1;
}
const int mod = 1e9 + 7;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= 6; ++j) {
for (int x = 1; x <= rollMax[j - 1]; ++x) {
for (int k = 1; k <= 6; ++k) {
if (k != j) {
f[i][k][1] = (f[i][k][1] + f[i - 1][j][x]) % mod;
} else if (x + 1 <= rollMax[j - 1]) {
f[i][j][x + 1] = (f[i][j][x + 1] + f[i - 1][j][x]) % mod;
}
}
}
}
}
int ans = 0;
for (int j = 1; j <= 6; ++j) {
for (int x = 1; x <= rollMax[j - 1]; ++x) {
ans = (ans + f[n][j][x]) % mod;
}
}
return ans;
}
};func dieSimulator(n int, rollMax []int) (ans int) {
f := make([][7][16]int, n+1)
for j := 1; j <= 6; j++ {
f[1][j][1] = 1
}
const mod = 1e9 + 7
for i := 2; i <= n; i++ {
for j := 1; j <= 6; j++ {
for x := 1; x <= rollMax[j-1]; x++ {
for k := 1; k <= 6; k++ {
if k != j {
f[i][k][1] = (f[i][k][1] + f[i-1][j][x]) % mod
} else if x+1 <= rollMax[j-1] {
f[i][j][x+1] = (f[i][j][x+1] + f[i-1][j][x]) % mod
}
}
}
}
}
for j := 1; j <= 6; j++ {
for x := 1; x <= rollMax[j-1]; x++ {
ans = (ans + f[n][j][x]) % mod
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with 3D Array | Time Complexity: O(n * 6 * 6 * m) where m = max(rollMax) |
| Dynamic Programming with 2D Array | Time Complexity: O(n * 6 * 6) |
| Memoization Search | – |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with 3D Array | O(n * 6 * maxRoll) | O(n * 6 * maxRoll) | Best for understanding the full DP state including roll index, face, and streak length |
| Dynamic Programming with 2D Array | O(n * 6) | O(n * 6) | Preferred optimized solution when reducing state dimensions for better performance |
Frequently asked questions
Is Dice Roll Simulation easy or hard?
Dice Roll Simulation is classified as a Hard problem because it requires careful state design in dynamic programming. The main challenge is handling consecutive roll constraints efficiently without exploding the state space.
Dice Roll Simulation Python/Java solution
Python and Java implementations typically use dynamic programming with either a 3D state dp[i][j][k] or an optimized 2D state dp[i][j]. Both compute transitions for the six dice faces and apply modulo 1e9+7 to avoid integer overflow.
How to solve Dice Roll Simulation in O(n)?
Use a dynamic programming table where dp[i][j] stores the number of sequences of length i ending with face j. Compute transitions using the total sequences from the previous step and subtract sequences that would exceed rollMax[j]. This avoids tracking streak length explicitly and keeps each iteration limited to the six faces.
What is the best approach for Dice Roll Simulation?
The most efficient approach uses dynamic programming. A 2D DP formulation tracks the number of sequences ending with each dice face and subtracts sequences that would violate the rollMax consecutive constraint. This reduces the state space compared to a full 3D DP while keeping the time complexity around O(n * 6).
Is Dice Roll Simulation asked at Google/Amazon/Meta?
Dice Roll Simulation represents the type of constraint-based dynamic programming problem commonly asked in interviews at companies like Google, Amazon, and Meta. The focus is on modeling state transitions and optimizing DP dimensions rather than brute-force enumeration.
What data structure is used in Dice Roll Simulation?
The solution primarily uses arrays for dynamic programming states. A 3D array tracks roll index, face value, and consecutive count, while the optimized approach uses a 2D DP array plus prefix totals to manage transitions efficiently.
What is the time complexity of Dice Roll Simulation?
The straightforward dynamic programming solution with a 3D state runs in O(n * 6 * maxRoll) time because it tracks the roll index, dice face, and streak length. An optimized 2D DP version reduces the complexity to roughly O(n * 6) by removing the explicit streak dimension and adjusting counts using previous states.