2350. Shortest Impossible Sequence of Rolls
Problem Description
In this problem, we are given two inputs: an integer array rolls
of size n
, which represents the outcomes of rolling a k
-sided dice n
times, with k
being the second input ā a positive integer. The dice have sides numbered from 1
to k
.
We need to find the length of the shortest sequence of rolls that is not present in the given rolls
array. A sequence of rolls is defined by the numbers that are obtained when rolling the k
-sided dice some number of times. The key point is that we're not looking for a sequence that must be in consecutive order in rolls
, but the numbers must appear in the same order as they would in the dice rolls.
To put it in simple words: imagine you are writing down each result of rolling a k
-sided dice on a piece of paper, one after another. You now have to find the smallest length of a list of numbers that you could never write down only by using the numbers in the exact same order they appear in the rolls
array.
Intuition
The solution to this problem relies on the observation that the length of the shortest absent rolls sequence depends directly on the variety of numbers in each segment of the array. Since we want to find the shortest sequence that can't be found in rolls
, we can look at the input array as a series of segments where, once we encounter all k
unique dice numbers, we can start looking for a new sequence.
The approach for the solution is to track the unique numbers we roll with a set s
. As we iterate over the rolls
:
- We add each number to the set
s
. - We check if the size of the set
s
has reachedk
. If it has, it means we've seen all possible outcomes from the dice in this segment. - Once we see that all numbers have appeared, it implies that any sequence of length equal to the current answer
ans
can be constructed from the segment, so we begin searching for the next longer sequence that cannot be constructed, by incrementingans
by 1. - We then clear the set
s
to start checking for the next segment.
With this strategy, each time we complete a full set of k
unique numbers, the length of the shortest missing sequence increases, since we're able to construct any shorter sequence up to that point. The increment in ans
represents the sequential nature of sequences that can't be found in rolls
. When we have gone through all the elements in rolls
, the value stored in ans
will be the length of the shortest sequence that didn't appear in the rolls
.
Learn more about Greedy patterns.
Solution Approach
The solution utilizes a greedy approach which aims to construct the shortest missing sequence incrementally.
Algorithm:
-
We initialize an empty set
s
. The purpose of this set is to store unique dice roll outcomes from therolls
array as we iterate through it. -
We also define an integer
ans
, which is initialized at1
. This variable represents the length of the current shortest sequence that cannot be found inrolls
. -
We iterate through every integer
v
in therolls
array and add the roll outcomev
to the sets
every time. This is our way of keeping track of the outcomes we have seen so far. By using a set, we automatically ensure that each outcome is only counted once. If a particular number repeats inrolls
, it does not affect our counting in the sets
. -
After each insertion, we check if the size of the set
s
has reached the sizek
. This step is key to the implementation, since reaching a set size ofk
implies that we have seen all possible outcomes that could be the result of a dice roll.-
If and when the set size is
k
, it means we have found a sequence of rolls of lengthans
that can be created usingrolls
. Consequently, we can't be looking for sequences of this length anymore; we need to look for a longer sequence that cannot be generated. Thus, we incrementans
by1
. -
To start looking for the next shortest missing sequence, we need to clear the set
s
. By doing so, we reset our tracking of unique dice outcomes.
-
-
The loop repeats until all dice rolls in
rolls
have been examined. By now,ans
will be one more than the length of the longest sequence of rolls that can be found inrolls
. Therefore, ans will be the shortest sequence length that cannot be constructed fromrolls
.
Data Structures:
-
The use of a set is essential in this approach. The set allows us to maintain a collection of unique items, which is perfect for keeping track of which dice numbers we have encountered. As a set doesn't store duplicates, it's also very efficient for this use case.
-
The use of an integer,
ans
, to represent the length of the sequence we're currently looking for.
Patterns:
- The pattern in the solution approach follows a greedy algorithm. Greedy algorithms make the locally optimum choice at each step with the intent of finding the global optimum.
In summary, while iterating over the array rolls
, we are greedily increasing the length of the sequence ans
whenever we confirm that a sequence of that length can indeed be created using the rolls seen so far. The final value of ans
when we have completed our iteration is the length of the shortest sequence that cannot be constructed from rolls
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example:
Assume we are given an array rolls = [1, 2, 3, 3, 2]
, and the dice has k = 3
sides. Our goal is to find the length of the shortest sequence of dice rolls that is not represented in rolls
.
-
First, we initialize an empty set
s
and an integerans
with a value of1
. The sets
will track unique dice roll outcomes, andans
represents the length of the current shortest sequence not found inrolls
. -
We begin iterating over each element in
rolls
:-
We add
1
to the sets
, which becomes{1}
. -
No increment to
ans
is needed since the set does not yet contain allk
unique rolls. -
We move to the next roll, adding
2
to the set. Nows = {1, 2}
. -
We still don't need to increment
ans
ass
does not contain allk
unique rolls. -
We add the next roll,
3
, to the set. Nows = {1, 2, 3}
. -
Since
s
now containsk
unique numbers (all possible outcomes of the dice), we have seen at least one of each possible roll. At this point, we can construct any sequence of length1
with the numbers ins
, so we incrementans
to2
and clear the sets
to start tracking the next sequence. -
The next roll is a
3
. We add it to the now-empty sets
, resulting ins = {3}
. -
The set still doesn't contain all
k
unique numbers, so we don't incrementans
. -
Finally, we add the last roll,
2
, to the set. Nows = {2, 3}
. -
Since we have reached the end of the
rolls
array and the sets
does not containk
unique numbers, we stop here.
-
-
After completing the iteration, the value of
ans
stands at2
.
Therefore, the length of the shortest sequence of rolls that cannot be found in rolls
is 2
. This means there is no sequence of two rolls in the order they were rolled that we did not see at least once in the given rolls
array.
Solution Implementation
1from typing import List
2
3class Solution:
4 def shortestSequence(self, rolls: List[int], k: int) -> int:
5 # `shortestSeqLength` will hold the length of the shortest sequence that is not a subsequence of `rolls`
6 shortestSeqLength = 1
7
8 # `uniqueNumbers` will keep track of the unique numbers we have seen in the current subsequence
9 uniqueNumbers = set()
10
11 # Iterate over each number in the `rolls` list
12 for number in rolls:
13 # Add the number to the set of unique numbers
14 uniqueNumbers.add(number)
15
16 # Check if we have seen all `k` different numbers
17 if len(uniqueNumbers) == k:
18 # If true, we can form a new subsequence which will not be a subsequence of the current `rolls`
19 shortestSeqLength += 1
20
21 # Clear the set to start tracking a new subsequence
22 uniqueNumbers.clear()
23
24 # Return the length of the shortest sequence that is not a subsequence of `rolls`
25 return shortestSeqLength
26
1class Solution {
2 public int shortestSequence(int[] rolls, int k) {
3 // Initialize a set to keep track of unique elements
4 Set<Integer> set = new HashSet<>();
5 // Initialize the answer variable which represents the shortest sequence
6 int answer = 1;
7
8 // Iterate through each number in the rolls array
9 for (int number : rolls) {
10 // Add the current number to the set
11 set.add(number);
12 // Check if the set size equals k, meaning all numbers are present
13 if (set.size() == k) {
14 // Reset the set for the next sequence
15 set.clear();
16 // Increment the answer value, as we've completed a sequence
17 answer++;
18 }
19 }
20 // Return the count of the shortest sequence
21 return answer;
22 }
23}
24
1#include <vector>
2#include <unordered_set>
3
4class Solution {
5public:
6 // Function to find the shortest sequence that contains every number from 1 to k
7 int shortestSequence(vector<int>& rolls, int k) {
8 unordered_set<int> numbers; // Set to store unique numbers
9 int sequenceLength = 1; // Initialize the sequence length as 1
10
11 // Iterate over the roll values
12 for (int roll : rolls) {
13 numbers.insert(roll); // Insert the current roll value into the set
14 // If the size of the set equals k, we have found a full sequence
15 if (numbers.size() == k) {
16 numbers.clear(); // Clear the set for the next sequence
17 ++sequenceLength; // Increment the sequence length counter
18 }
19 }
20
21 return sequenceLength; // Return the shortest sequence length
22 }
23};
24
1// Importing Set from the ES6 standard library
2import { Set } from "typescript-collections";
3
4// Function to find the shortest sequence that contains every number from 1 to k
5function shortestSequence(rolls: number[], k: number): number {
6 const numbers: Set<number> = new Set(); // Set to store unique numbers
7 let sequenceLength: number = 1; // Initialize the sequence length as 1
8
9 // Iterate over the roll values
10 rolls.forEach(roll => {
11 numbers.add(roll); // Insert the current roll value into the set
12 // If the size of the set equals k, we have found a full sequence
13 if (numbers.size === k) {
14 numbers.clear(); // Clear the set for the next sequence
15 sequenceLength++; // Increment the sequence length counter
16 }
17 });
18
19 return sequenceLength; // Return the shortest sequence length
20}
21
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n)
where n
is the length of the input list rolls
. This is because the code iterates through each roll exactly once. Inside the loop, adding an element to the set s
and checking its length are both O(1)
operations. When s
reaches the size k
, it is cleared, which is also an O(1)
operation because it happens at most n/k
times and does not depend on the size of the set when cleared.
Space Complexity
The space complexity is O(k)
because the set s
is used to store at most k
unique values from the rolls
list at any given time. The other variables, ans
and v
, use a constant amount of space, hence they contribute O(1)
, which is negligible in comparison to O(k)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which technique can we use to find the middle of a linked list?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!