Skip to main content
Talentd

Shortest Impossible Sequence of Rolls - Solution & Explanation

HardArrayHash TableGreedy10 min readAsked at: Google, Bloomberg
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You receive an array rolls representing dice outcomes and an integer k representing the number of faces on the die. The task is to find the length of the shortest sequence of rolls (values 1..k) that cannot appear as a subsequence of the given array.

Approach 1: Greedy Set Tracking (O(n) time, O(k) space)

The key observation: if the array contains every face from 1..k, then any sequence of length 1 is possible. If it contains two complete sets of 1..k, then any sequence of length 2 is possible, and so on. Iterate through rolls and track distinct values in a hash set. Each time the set size reaches k, you discovered one complete "round" containing all faces. Clear the set and increment a counter. If you can build x full rounds, then every sequence of length x can be formed as a subsequence, so the shortest impossible sequence has length x + 1. This greedy observation reduces the problem to counting complete collections of faces using a hash table while scanning the array.

Approach 2: Sliding Window Coverage (O(n) time, O(k) space)

Another perspective treats the problem as repeatedly finding segments that contain all k faces. Maintain a frequency structure and expand a window while scanning the array. Once the window covers every face from 1..k, you count one valid segment, reset the tracking structure, and continue scanning for the next complete coverage. Each completed segment represents the ability to form another subsequence position. When the scan ends, the answer is again the number of complete segments plus one. This approach uses a greedy-style reset strategy combined with window-style iteration.

Recommended for interviews: The greedy set-tracking approach is what most interviewers expect. It shows you recognize the combinatorial insight that each full coverage of 1..k guarantees all subsequences of that length. A brute-force attempt would try constructing subsequences and checking feasibility, but recognizing the greedy counting trick demonstrates strong pattern recognition and leads to the optimal O(n) solution.

Approach 1: Greedy Approach

The idea is to track how many complete sets of roll numbers from 1 to k you can possibly form before a configuration becomes impossible.

Each time we encounter a complete set of `1` to `k`, increment the counter. The moment when you can't form another complete set is when you'd require additional numbers, thus making it impossible.

We use a set to keep track of unique rolls seen so far. Each time the set reaches size `k`, it means we can form a complete sequence; we clear the set and increment our counter.
The answer is 1 more than the number of complete sets we've seen.

Code

PythonJavaScriptC++JavaCC#

Python

JavaScript

C++

Java

C

C#

Complexity

Time Complexity: O(n), where `n` is the length of `rolls` since we iterate through the list once.
Space Complexity: O(k), since at most we store `k` numbers in the set.

Try this approach in the editor →

Approach 2: Sliding Window Approach

Using a sliding window technique to check every subsequence to see their validity could be effective but would face limitations due to the length of `rolls`. We instead use distinct counting across spans to cleverly deduce possible full sequences once iteration moves coverage.

This technique isn't straightforward and not directly applied due to resource limits, contrasts with efficient greedy strategy.

Here, visualization is using parts of distinct sequence optimizations across sections without full set.

Code

PythonJavaScriptC++

Python

JavaScript

C++

Complexity

Time Complexity: O(n * k), where checking all range length positions.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(n), where `n` is the length of `rolls` since we iterate through the list once.
Space Complexity: O(k), since at most we store `k` numbers in the set.

Sliding Window Approach

Time Complexity: O(n * k), where checking all range length positions.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Set TrackingO(n)O(k)Best general solution. Quickly counts complete sets of dice faces while scanning the array.
Sliding Window CoverageO(n)O(k)Useful when thinking in terms of segments that contain all k values.

Video Solution

Biweekly Contest 83 | 2350. Shortest Impossible Sequence of Rolls • codingMohan • 3,586 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Shortest Impossible Sequence of Rolls easy or hard?
The problem is labeled Hard because the greedy insight is not obvious at first. Once you recognize that each complete set of faces guarantees all subsequences of that length, the implementation becomes straightforward and linear time.
Shortest Impossible Sequence of Rolls Python/Java solution
Most implementations follow the same greedy idea: iterate through the array, track distinct values in a set, and reset after collecting all k faces. This logic translates directly into Python, Java, C++, and JavaScript with O(n) runtime and O(k) memory.
How to solve Shortest Impossible Sequence of Rolls in O(n)?
Iterate through the rolls array and maintain a set of distinct values encountered. When the set reaches size k, you found one complete coverage of all dice faces. Increment a counter and clear the set to start tracking the next round. After scanning the entire array, return counter + 1 as the shortest impossible sequence length.
What is the best approach for Shortest Impossible Sequence of Rolls?
The greedy set-tracking approach is the most efficient. Scan the rolls array while collecting unique faces in a hash set. Every time all k faces appear, you complete one full round and reset the set. If x rounds are found, the shortest impossible sequence length is x + 1. The algorithm runs in O(n) time with O(k) extra space.
Is Shortest Impossible Sequence of Rolls asked at Google/Amazon/Meta?
Problems involving greedy counting and subsequence feasibility frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require identifying missing subsequences or counting complete sets are common in algorithm rounds.
What data structure is used in Shortest Impossible Sequence of Rolls?
A hash set or boolean frequency array is typically used to track which dice faces have appeared in the current segment. The structure allows constant-time checks and resets once all k faces are observed.
What is the time complexity of Shortest Impossible Sequence of Rolls?
The optimal solution runs in O(n) time where n is the number of rolls. Each roll is processed once while updating a hash set or frequency structure. Space complexity is O(k) because you only track the k possible dice faces.

Ready to solve this problem?

Practice Shortest Impossible Sequence of Rolls with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays