Shortest Impossible Sequence of Rolls — LeetCode 2350 Python Solution

The 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].

Example

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.

Python solution

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

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2350. Shortest Impossible Sequence of Rolls is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems