Scale Engineer

Shortest Impossible Sequence of Rolls

Hard
#2140Time: O(n * ans), where n is the number of rolls and `ans` is the length of the shortest impossible sequence. For each length `ans`, we iterate through the `rolls` array once.Space: O(n), where n is the number of rolls. We use two arrays of size n+1 to store DP results for the current and previous lengths.
Patterns
Greedy
Data structures
ArrayHash Table

Prompt

You are given an integer array rolls of length n and an integer k. You roll a k sided dice numbered from 1 to k, n times, where the result of the ith roll is rolls[i].

Return the length of the shortest sequence of rolls so that there's no such subsequence in rolls.

A sequence of rolls of length len is the result of rolling a k sided dice len times.

 

Example 1:

Input: rolls = [4,2,1,2,3,3,2,4,1], k = 4
Output: 3
Explanation: Every sequence of rolls of length 1, [1], [2], [3], [4], can be taken from rolls.
Every sequence of rolls of length 2, [1, 1], [1, 2], ..., [4, 4], can be taken from rolls.
The sequence [1, 4, 2] cannot be taken from rolls, so we return 3.
Note that there are other sequences that cannot be taken from rolls.

Example 2:

Input: rolls = [1,1,2,2], k = 2
Output: 2
Explanation: Every sequence of rolls of length 1, [1], [2], can be taken from rolls.
The sequence [2, 1] cannot be taken from rolls, so we return 2.
Note that there are other sequences that cannot be taken from rolls but [2, 1] is the shortest.

Example 3:

Input: rolls = [1,1,3,2,2,2,3,3], k = 4
Output: 1
Explanation: The sequence [4] cannot be taken from rolls, so we return 1.
Note that there are other sequences that cannot be taken from rolls but [4] is the shortest.

 

Constraints:

  • n == rolls.length
  • 1 <= n <= 105
  • 1 <= rolls[i] <= k <= 105

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to count the number of distinct subsequences for each possible length. We iterate through lengths L = 1, 2, 3, ... and for each length, we calculate how many unique subsequences of that length can be formed from the rolls array. The first length L for which this count is less than the total number of possible sequences of that length (k^L) is the answer.

Algorithm

  1. We are looking for the smallest length L such that the number of distinct subsequences of rolls of length L is less than k^L.
  2. We can iterate L from 1 upwards.
  3. For each L, we calculate the total number of distinct subsequences of length L that can be formed from the rolls array.
  4. Let dp[i][j] be the number of distinct subsequences of length j in the prefix rolls[0...i-1].
  5. The recurrence relation is: dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] - dp[p][j-1]), where p is the index of the previous occurrence of the element rolls[i-1]. This formula counts subsequences not using rolls[i-1] (dp[i-1][j]) and those formed by appending rolls[i-1] to shorter subsequences, avoiding double counting.
  6. We can optimize space by noticing that computing the column for length L only requires the column for length L-1. So we can use two arrays, one for the previous length and one for the current length.
  7. For each L, we compute dp[n][L]. If dp[n][L] < k^L, we have found our answer, and we return L.
  8. We must handle potential overflow when calculating k^L.

Walkthrough

Let dp[i][j] be the number of distinct subsequences of length j that can be formed using the prefix of the rolls array of length i (i.e., rolls[0...i-1]). Our goal is to find the smallest j such that dp[n][j] < k^j.

The recurrence relation for dp[i][j] is derived by considering the element rolls[i-1]:

  • Subsequences of length j in rolls[0...i-1] that do not include rolls[i-1] are the same as subsequences of length j in rolls[0...i-2]. Their count is dp[i-1][j].
  • Subsequences of length j in rolls[0...i-1] that do include rolls[i-1] as their last element are formed by taking any distinct subsequence of length j-1 from rolls[0...i-2] and appending rolls[i-1]. The number of such new subsequences is dp[i-1][j-1]. However, this might lead to double counting if rolls[i-1] has appeared before. If the previous occurrence of rolls[i-1] was at index p-1, then any subsequence of length j-1 from rolls[0...p-2] extended with rolls[i-1] has already been counted. We must subtract these, which amounts to dp[p-1][j-1].

So, the full recurrence is: dp[i][j] = dp[i-1][j] + dp[i-1][j-1] - dp[p-1][j-1], where p is the 1-based index of the previous occurrence of rolls[i-1].

We can optimize the space from O(n*ans) to O(n) by using only two arrays to store the DP results for the current and previous lengths.

import java.util.Arrays; class Solution {    public int shortestImpossibleSequenceOfRolls(int[] rolls, int k) {        int n = rolls.length;        // dp for length len-1. Initially for len=0, there's 1 empty subsequence.        long[] prevDp = new long[n + 1];        Arrays.fill(prevDp, 1);         for (int len = 1; len <= n + 1; len++) {            long kPowLen = 1;            // Calculate k^len with overflow check            for (int i = 0; i < len; i++) {                if (kPowLen > Long.MAX_VALUE / k) {                    kPowLen = Long.MAX_VALUE; // Represents a very large number                    break;                }                kPowLen *= k;            }             long[] currDp = new long[n + 1]; // dp for length len            int[] last = new int[k + 1]; // Stores last seen 1-based index of a roll value             for (int i = 1; i <= n; i++) {                // Number of subsequences of length 'len' in rolls[0...i-2]                currDp[i] = currDp[i - 1];                                // New subsequences formed by appending rolls[i-1]                long toAdd = prevDp[i - 1];                int rollValue = rolls[i - 1];                if (last[rollValue] > 0) {                    // Subtract subsequences that would be duplicates                    toAdd -= prevDp[last[rollValue] - 1];                }                currDp[i] += toAdd;            }             if (currDp[n] < kPowLen) {                return len;            }            prevDp = currDp;        }                return n + 1; // Should not be reached given problem constraints    }}

Complexity

Time

O(n * ans), where n is the number of rolls and `ans` is the length of the shortest impossible sequence. For each length `ans`, we iterate through the `rolls` array once.

Space

O(n), where n is the number of rolls. We use two arrays of size n+1 to store DP results for the current and previous lengths.

Trade-offs

Pros

  • It is a systematic approach that correctly solves the problem.

  • The logic is based on a standard DP technique for counting distinct subsequences.

Cons

  • The time complexity is dependent on the answer, which can be large in some cases, leading to a Time Limit Exceeded error on certain test cases.

  • The implementation is more complex than the greedy approach, involving careful handling of DP states and potential numerical overflows.

Solutions

class Solution { public int shortestSequence ( int [] rolls , int k ) { Set < Integer > s = new HashSet <>(); int ans = 1 ; for ( int v : rolls ) { s . add ( v ); if ( s . size () == k ) { s . clear (); ++ ans ; } } return ans ; } }

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 →

Next problem