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 <= 105Problem Overview: You receive an array rolls representing dice outcomes and an integer k representing the number of faces on the die. The task is to find the length of the shortest sequence of rolls (values 1..k) that cannot appear as a subsequence of the given array.
Approach 1: Greedy Set Tracking (O(n) time, O(k) space)
The key observation: if the array contains every face from 1..k, then any sequence of length 1 is possible. If it contains two complete sets of 1..k, then any sequence of length 2 is possible, and so on. Iterate through rolls and track distinct values in a hash set. Each time the set size reaches k, you discovered one complete "round" containing all faces. Clear the set and increment a counter. If you can build x full rounds, then every sequence of length x can be formed as a subsequence, so the shortest impossible sequence has length x + 1. This greedy observation reduces the problem to counting complete collections of faces using a hash table while scanning the array.
Approach 2: Sliding Window Coverage (O(n) time, O(k) space)
Another perspective treats the problem as repeatedly finding segments that contain all k faces. Maintain a frequency structure and expand a window while scanning the array. Once the window covers every face from 1..k, you count one valid segment, reset the tracking structure, and continue scanning for the next complete coverage. Each completed segment represents the ability to form another subsequence position. When the scan ends, the answer is again the number of complete segments plus one. This approach uses a greedy-style reset strategy combined with window-style iteration.
Recommended for interviews: The greedy set-tracking approach is what most interviewers expect. It shows you recognize the combinatorial insight that each full coverage of 1..k guarantees all subsequences of that length. A brute-force attempt would try constructing subsequences and checking feasibility, but recognizing the greedy counting trick demonstrates strong pattern recognition and leads to the optimal O(n) solution.
The idea is to track how many complete sets of roll numbers from 1 to k you can possibly form before a configuration becomes impossible.
Each time we encounter a complete set of `1` to `k`, increment the counter. The moment when you can't form another complete set is when you'd require additional numbers, thus making it impossible.
We use a set to keep track of unique rolls seen so far. Each time the set reaches size `k`, it means we can form a complete sequence; we clear the set and increment our counter.
The answer is 1 more than the number of complete sets we've seen.
Time Complexity: O(n), where `n` is the length of `rolls` since we iterate through the list once.
Space Complexity: O(k), since at most we store `k` numbers in the set.
Using a sliding window technique to check every subsequence to see their validity could be effective but would face limitations due to the length of `rolls`. We instead use distinct counting across spans to cleverly deduce possible full sequences once iteration moves coverage.
This technique isn't straightforward and not directly applied due to resource limits, contrasts with efficient greedy strategy.
Here, visualization is using parts of distinct sequence optimizations across sections without full set.
Python
JavaScript
C++
Time Complexity: O(n * k), where checking all range length positions.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where `n` is the length of `rolls` since we iterate through the list once. |
| Sliding Window Approach | Time Complexity: O(n * k), where checking all range length positions. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Set Tracking | O(n) | O(k) | Best general solution. Quickly counts complete sets of dice faces while scanning the array. |
| Sliding Window Coverage | O(n) | O(k) | Useful when thinking in terms of segments that contain all k values. |
Biweekly Contest 83 | 2350. Shortest Impossible Sequence of Rolls • codingMohan • 3,427 views views
Watch 9 more video solutions →Practice Shortest Impossible Sequence of Rolls with our built-in code editor and test cases.
Practice on FleetCode