Welcome to Subscribe On Youtube
2350. Shortest Impossible Sequence of Rolls
Description
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 i^{th}
roll is rolls[i]
.
Return the length of the shortest sequence of rolls that cannot be taken from rolls
.
A sequence of rolls of length len
is the result of rolling a k
sided dice len
times.
Note that the sequence taken does not have to be consecutive as long as it is in order.
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 <= 10^{5}
1 <= rolls[i] <= k <= 10^{5}
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; } }

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

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

func shortestSequence(rolls []int, k int) int { s := map[int]bool{} ans := 1 for _, v := range rolls { s[v] = true if len(s) == k { ans++ s = map[int]bool{} } } return ans }