# Shortest Impossible Sequence of Rolls
**Difficulty:** HARD
[External](https://leetcode.com/problems/shortest-impossible-sequence-of-rolls)
Canonical: https://scaleengineer.com/dsa/problems/shortest-impossible-sequence-of-rolls
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Hash Table
---
## Problem
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
## Dynamic Programming by Counting Subsequences
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.
**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.
**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.
### Explanation
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.

```java
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
    }
}
```
### 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`.

## Greedy Single-Pass Approach
A highly efficient greedy approach can solve this problem in a single pass. The core idea is to determine how many complete sets of rolls (from 1 to `k`) we can form from consecutive, non-overlapping segments of the `rolls` array. Each time we find a segment containing all `k` possible rolls, it means we can successfully construct one more layer of sequences. The length of the shortest impossible sequence is one greater than the number of such complete segments found.
**Time:** O(n), where n is the number of rolls, as we iterate through the array only once. · **Space:** O(k) to store the set of seen roll values in the current segment.
**Pros:** Extremely efficient with linear time complexity.; Simple to implement and requires minimal space.; Passes all constraints, including large inputs for `n` and `k`.
**Cons:** The proof of correctness is based on a greedy choice and is less straightforward to formally prove compared to the DP approach.
### Explanation
Let's analyze why this greedy strategy works. We are looking for the smallest `L` such that some sequence of rolls of length `L` is not a subsequence of `rolls`. This is equivalent to finding the largest `L-1` for which *all* sequences of length `L-1` are subsequences of `rolls`.

Let's say we have found `count` disjoint segments in `rolls`, where each segment contains all numbers from 1 to `k`. Let these segments be `S_1, S_2, ..., S_{count}`.

**Claim 1: All sequences of length `count` are possible.**
Consider any sequence `[r_1, r_2, ..., r_{count}]`. We can find `r_1` in the first segment `S_1`. After finding `r_1`, we look for `r_2` in the rest of the `rolls` array, which includes `S_2, ..., S_{count}`. We can surely find `r_2` in `S_2`. We continue this process, finding `r_i` in segment `S_i`. Since the segments are disjoint and appear in order, we can always find the sequence `[r_1, ..., r_{count}]` as a subsequence of `rolls`. This means the shortest impossible sequence must have a length of at least `count + 1`.

**Claim 2: There exists an impossible sequence of length `count + 1`.**
After finding `count` such segments, the remainder of the `rolls` array does not contain a full set of `1..k`. This means there is at least one number, say `y`, that is missing from this remainder. If we construct a sequence of length `count+1` that requires `y` to be found in this remainder, that sequence will be impossible. The greedy strategy of finding the shortest possible segments ensures that we can construct such an impossible sequence. Therefore, the shortest impossible length is exactly `count + 1`.

The algorithm is to count these segments. We start with `ans = 1` (for the base case of length 1 sequences being impossible if not all `k` values are present at all). Each time we find a full set of `1..k`, we increment `ans`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int shortestImpossibleSequenceOfRolls(int[] rolls, int k) {
        int ans = 1;
        Set<Integer> seen = new HashSet<>();
        
        for (int roll : rolls) {
            seen.add(roll);
            if (seen.size() == k) {
                // Found a segment with all k numbers.
                // This means we can form one more layer of sequences.
                ans++;
                // Reset to find the next segment.
                seen.clear();
            }
        }
        
        return ans;
    }
}
```
### Algorithm
1. Initialize a variable `ans` to 1, representing the length of sequences we can currently form. Initially, we can only form sequences of length 0 (the empty sequence), so the first impossible length is 1.
2. Initialize an empty set, `seen`, to keep track of the unique roll values encountered in the current segment of `rolls`.
3. Iterate through the `rolls` array one by one.
4. For each `roll`, add it to the `seen` set.
5. After adding a roll, check if the size of the `seen` set has become equal to `k`.
6. If `seen.size() == k`, it means we have found a segment in `rolls` that contains all possible outcomes from 1 to `k`. This allows us to extend all previously formable sequences by one more arbitrary roll. Therefore, we increment `ans`.
7. After incrementing `ans`, we clear the `seen` set to start looking for the next complete segment.
8. After iterating through all the rolls, the final value of `ans` is the length of the shortest impossible sequence.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
class Solution { public: int shortestSequence ( vector < int >& rolls , int k ) { unordered_set < int > s ; int ans = 1 ; for ( int v : rolls ) { s . insert ( v ); if ( s . size () == k ) { s . clear (); ++ ans ; } } return ans ; } };
```

### Python

```python
class Solution : def shortestSequence ( self , rolls : List [ int ], k : int ) -> int : ans = 1 s = set () for v in rolls : s . add ( v ) if len ( s ) == k : ans += 1 s . clear () return ans
```