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.length1 <= n <= 1051 <= rolls[i] <= k <= 105The key idea behind #2350 Shortest Impossible Sequence of Rolls is to observe how many complete sets of dice values from 1..k appear in the array. If you can repeatedly collect every value at least once, it means many different subsequences can be formed. The moment a full set of values is seen, it guarantees that all sequences up to a certain length are constructible.
A greedy strategy works well here. Traverse the array while tracking which dice values have appeared using a hash set or boolean array. Each time all k values are encountered, you reset the tracker and continue scanning. The number of such completed groups determines how many sequence lengths are fully possible, and the next length becomes impossible.
This approach avoids generating subsequences and instead relies on counting coverage cycles. The traversal runs in O(n) time while maintaining a structure of size k, giving O(k) space complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy scan with hash/boolean tracking of 1..k values | O(n) | O(k) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
How can you find the minimum index such that all sequences of length 1 can be formed from the start until that index?
Starting from the previous minimum index, what is the next index such that all sequences of length 2 can be formed?
Can you extend the idea to sequences of length 3 and more?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Every time all values from 1 to k appear, it ensures that many combinations of subsequences of that length can be constructed. By counting these complete coverage cycles, we know when a longer sequence length can no longer be guaranteed to exist.
Problems involving greedy counting, coverage of elements, and subsequence reasoning are common in FAANG-style interviews. While this exact question may not always appear, similar patterns testing greedy thinking and set coverage frequently do.
A boolean array or hash set works best to track which dice values have been observed in the current segment. Since values range from 1 to k, a boolean array is typically more efficient and keeps the space complexity at O(k).
The optimal approach uses a greedy scan of the rolls array while tracking which dice values from 1 to k have appeared. Each time all k values are seen, the tracker resets. The number of such completed groups helps determine the smallest sequence length that cannot be formed.