Shortest Impossible Sequence of Rolls - Video Solutions
Biweekly Contest 83 | 2350. Shortest Impossible Sequence of Rolls
Shortest Impossible Sequence of Rolls - Video Solution
Watch 10 video solutions for Shortest Impossible Sequence of Rolls, a hard level problem involving Array, Hash Table, Greedy. This walkthrough by codingMohan has 3,586 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.length1 <= n <= 1051 <= 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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Set Tracking | O(n) | O(k) | Best general solution. Quickly counts complete sets of dice faces while scanning the array. |
| Sliding Window Coverage | O(n) | O(k) | Useful when thinking in terms of segments that contain all k values. |