{x}
blog image

Shortest Impossible Sequence of Rolls

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.length
  • 1 <= n <= 105
  • 1 <= rolls[i] <= k <= 105

Solution Explanation

This problem asks for the length of the shortest sequence of dice rolls that cannot be found as a subsequence within the given rolls array. The key insight is that we're looking for the minimum length sequence where all possible dice outcomes (1 to k) haven't been seen.

The optimal solution leverages a greedy approach and utilizes a set to efficiently track the unique dice roll outcomes encountered so far.

Algorithm:

  1. Initialization: Initialize a set (or HashSet in Java, unordered_set in C++, map[int]bool in Go) to store the unique dice rolls encountered. Initialize ans (the length of the shortest impossible sequence) to 1, representing a single roll sequence.

  2. Iteration: Iterate through the rolls array.

  3. Add to Set: For each roll v, add it to the set.

  4. Check for Completion: If the size of the set equals k (meaning all possible dice outcomes from 1 to k have been observed), increment ans (we've completed a subsequence containing all possible rolls), and clear the set to start counting a new sequence.

  5. Return: After iterating through all rolls, return ans. This represents the length of the shortest sequence where at least one dice outcome was missing, thus making it an impossible subsequence in the original rolls.

Time Complexity: O(n), where n is the length of the rolls array. This is because we iterate through the array once. The set operations (insertion and checking size) have amortized constant time complexity.

Space Complexity: O(k), where k is the number of sides on the dice. This is the maximum size of the set, which stores unique dice rolls encountered.

Code Explanation (Python):

class Solution:
    def shortestSequence(self, rolls: List[int], k: int) -> int:
        ans = 1  # Initialize the shortest impossible sequence length to 1
        s = set() # Initialize a set to store unique dice rolls
        for v in rolls: # Iterate through the rolls array
            s.add(v) # Add the current roll to the set
            if len(s) == k: # Check if all k dice outcomes have been seen
                ans += 1 # Increment the sequence length
                s.clear() # Clear the set to start counting a new sequence
        return ans

The other language implementations (Java, C++, Go) follow the same logic, with only syntactic differences in the use of sets and data structures. The core algorithm remains consistent across all languages.