Shortest Impossible Sequence of Rolls

Hard

Asked by:

5 views

Topics:

Arrays

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 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 <= 10⁵
1 <= rolls[i] <= k <= 10⁵

Try coding it in LeetCode

Shortest Impossible Sequence of Rolls

Hard

Asked by:

5 views

Topics:

Arrays

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 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 <= 10⁵
1 <= rolls[i] <= k <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for `k` (the number of sides on the die) and the length of the `rolls` array? What happens if `k` is 0 or negative?
Can the `rolls` array be empty or contain zero values? What should I return if the rolls array is empty?
If there are multiple shortest impossible sequences, is any one acceptable as output?
Are the numbers in the `rolls` array guaranteed to be positive integers, and specifically, will they always be within the range [1, k] inclusive?
Could you provide an example where the shortest impossible sequence is longer than 1?

Brute Force Solution

Approach

The main idea is to try out all possible sequences of dice rolls, starting with the smallest ones. We check each sequence to see if it can be formed from the given rolls, and we stop as soon as we find one that can't.

Here's how the algorithm would work step-by-step:

Start by considering the simplest sequence of rolls: a single roll of '1'.
Check if the given list of rolls contains the sequence '1'.
If it does not, then '1' is the shortest impossible sequence, and we're done.
If it does, then consider the next possible sequence: '2'.
Check if the given list of rolls contains the sequence '2'.
Continue this process, incrementing the roll value we are testing, until you arrive at the value k.
Once we've checked all single roll sequences up to the value of k, move on to sequences of two rolls. Start with '1, 1'.
Check if the given rolls contain the sequence '1, 1' in order.
If not, '1, 1' is the answer. Otherwise, proceed to the next sequence such as '1, 2'.
Keep creating longer sequences and checking if they exist in the rolls.
As soon as you find a sequence that *doesn't* exist in the given rolls, you've found the shortest impossible sequence.

Code Implementation

def find_shortest_impossible_sequence(rolls, k_value):
    sequence_length = 1

    while True:
        # Generate all possible sequences of the current length.
        possible_sequences = generate_sequences(sequence_length, k_value)

        for sequence in possible_sequences:
            if not is_subsequence(sequence, rolls):
                # If sequence not found, its the answer.
                return sequence

        sequence_length += 1

def generate_sequences(sequence_length, k_value):
    if sequence_length == 0:
        return [[]]

    smaller_sequences = generate_sequences(sequence_length - 1, k_value)
    sequences = []

    for i in range(1, k_value + 1):
        for sequence in smaller_sequences:
            sequences.append(sequence + [i])

    return sequences

def is_subsequence(subsequence, rolls):
    subsequence_index = 0
    rolls_index = 0

    while subsequence_index < len(subsequence) and rolls_index < len(rolls):
        if subsequence[subsequence_index] == rolls[rolls_index]:
            subsequence_index += 1
        rolls_index += 1

    # Check if the subsequence was fully matched.
    return subsequence_index == len(subsequence)

Big(O) Analysis

Time Complexity

O(k^L * n) – The algorithm iterates through sequences of increasing length L, where each roll in the sequence can be any of the k possible values (1 to k). For each sequence of length L, the number of such sequences is k^L. For each sequence, the algorithm searches for it within the given list of n rolls. Searching for each sequence of length L in the given array takes O(n) in the worst case. Thus, the overall time complexity is O(k^L * n), where L is the length of the shortest impossible sequence.

Space Complexity

O(K^L) – The plain English description outlines a brute-force approach that explores all possible sequences of dice rolls up to a certain length. Let K be the number of possible rolls on a single die (e.g., K=6 for a standard die), and L be the maximum length of the sequences being checked. The number of such sequences grows exponentially as K^1 + K^2 + ... K^L, where the dominant term is K^L. Thus, this approach implicitly generates and checks all combinations of dice rolls up to length L, contributing to space complexity if we needed to store all possible sequences up to the shortest impossible one. However, the problem description does not indicate we store all these sequences. If we store a single sequence of maximum length L at a time, our algorithm has a space complexity of O(L), since it has to create and store the current sequence it is checking. The prompt also mentions the value k, which is the range of numbers on the die; assuming the sequence is composed of rolls from 1 to k and the length is L, then the number of possible sequences is O(k^L).

Optimal Solution

Approach

The goal is to find the shortest sequence of dice rolls that you *cannot* create from a given set of rolls. The fastest way involves checking which numbers are present and building the smallest missing sequence from there.

Here's how the algorithm would work step-by-step:

First, count how many times each number from 1 to 'k' appears in the given rolls.
Then, imagine trying to build every possible sequence of length 1, then length 2, and so on.
For each sequence length, start by considering the sequence of all 1s, then 1s and 2s, etc. Think of these sequences in increasing order.
For each sequence, check if you can make it from the given rolls, using the counts you have.
If a number appears in your current sequence more times than the count we found in the initial rolls, we can't make it, and this sequence is considered not doable.
If we find a sequence that we cannot make, we immediately know it is the shortest impossible sequence.
If we are able to make all sequences of a certain length, we increase the length and look for a missing sequence again.

Code Implementation

def shortest_impossible_sequence(rolls, k):
    roll_counts = [0] * (k + 1)

    for roll in rolls:
        roll_counts[roll] += 1

    sequence_length = 1

    while True:
        start_sequence = [1] * sequence_length
        end_sequence = [k] * sequence_length

        current_sequence = start_sequence.copy()
        sequence_number = 0

        while True:
            temp_counts = roll_counts.copy()
            possible = True

            # Check if we can form the current sequence.
            for number in current_sequence:
                if temp_counts[number] > 0:
                    temp_counts[number] -= 1
                else:
                    possible = False
                    break

            if not possible:
                return sequence_length

            if current_sequence == end_sequence:
                break

            # Generate the next sequence.
            index = sequence_length - 1
            while index >= 0 and current_sequence[index] == k:
                current_sequence[index] = 1
                index -= 1

            if index >= 0:
                current_sequence[index] += 1
            else:
                break

        #If all sequences of current length are possible,
        #increase the sequence length and try again.
        sequence_length += 1

Big(O) Analysis

Time Complexity

O(n*k) – The first step involves iterating through the 'n' rolls to count the occurrences of each number from 1 to 'k'. This step takes O(n) time, as 'k' is constant in this phase. Next, the algorithm iteratively checks sequences of increasing length, up to some maximum length. Checking each sequence involves comparing the count of each number in the sequence with the initial counts found from the rolls. In the worst case we might have to form and check approximately k number of sequences before we find the shortest sequence, and each comparison inside the checking loop costs O(n) where k is the number of distinct rolls, and n is the total number of rolls. Combining these steps the total complexity becomes O(n*k). Note the length of the shortest sequence in the worst case will be related to k

Space Complexity

O(k) – The algorithm uses an array to count the occurrences of each number from 1 to k in the input rolls. This count array takes O(k) space, where k is the number of possible values on the dice. No other significant auxiliary data structures are used; the search for the impossible sequence primarily uses iterative logic without storing intermediate sequences. Therefore, the overall auxiliary space complexity is dominated by the count array.

Edge Cases

Case	How to Handle
rolls is null or empty	Return 1 immediately, as any sequence of length 1 is impossible.
k is zero or negative	Return 1 immediately, as a zero or negative k is invalid, leading to an impossible sequence of length 1.
rolls contains only one distinct value, and that value is 'k'	If all rolls are equal to k, the shortest impossible sequence is of length 2 because we can only make 'k' and thus cannot complete the sequence 1 to k.
k is 1	Return 2 if the rolls contains no 1 otherwise return 1, the next missing integer.
rolls contains very large numbers or is extremely long	The size of rolls and the actual roll values themselves should not cause errors as we only care about the range of 1 to k.
rolls contains numbers outside the range [1, k]	Ignore values outside the range of [1, k] as they don't contribute to forming the sequence from 1 to k.
k is a very large number	The algorithm's memory usage depends on the range 'k', so a very large k might cause memory issues and the solution must use memory efficiently.
rolls does not contain all numbers between 1 and k	The solution should find the shortest sequence that's not present, even if not all numbers from 1 to k are in rolls.