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 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.
JavaScript
C++
Java
C
C#
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.
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. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,241 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