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

Return _the length of theshortest 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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5

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

1
2
3
4

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

Solution

Method 1 – Greedy Set Collection

Intuition

We want the shortest sequence length that cannot be formed as a subsequence. Each time we collect all k faces in the rolls, we can form all sequences of that length. The answer is the number of complete sets of k we can collect, plus one.

Approach

  1. Iterate through rolls, collecting unique numbers in a set.
  2. When the set reaches size k, increment the answer and clear the set.
  3. The answer is the number of rounds plus one.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.*;
class Solution {
    public int shortestSequence(int[] rolls, int k) {
        Set<Integer> seen = new HashSet<>();
        int ans = 1;
        for (int r : rolls) {
            seen.add(r);
            if (seen.size() == k) {
                ans++;
                seen.clear();
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def shortestSequence(self, rolls: list[int], k: int) -> int:
        seen = set()
        ans = 1
        for r in rolls:
            seen.add(r)
            if len(seen) == k:
                ans += 1
                seen.clear()
        return ans

Complexity

  • ⏰ Time complexity: O(n) — Each roll is processed once.
  • 🧺 Space complexity: O(k) — For the set of seen numbers.