Shortest Impossible Sequence of Rolls - Practice Coding Problems

Shortest Impossible Sequence of Rolls - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: rolls = [4,2,1,2,3,3,2,4,1], k = 4

› Output: 2

💡 Note: We can form any sequence of length 1: [1], [2], [3], [4] all appear in rolls. For length 2, we need all possible pairs, but [1,1] never appears as a subsequence, so answer is 2.

Example 2 — Immediate Missing

$ Input: rolls = [1,1,2,2], k = 4

› Output: 1

💡 Note: Values 3 and 4 never appear in rolls, so sequences [3] and [4] are impossible. The shortest impossible sequence has length 1.

Example 3 — Longer Sequence

$ Input: rolls = [1,1,1,2,2,2,3,3,3], k = 3

› Output: 2

💡 Note: All length 1 sequences appear: [1], [2], [3]. But some length 2 sequences like [1,2] don't appear as subsequences, so answer is 2.

Constraints

1 ≤ rolls.length ≤ 10⁵
1 ≤ rolls[i], k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array of dice rolls and number of sides k

Process

Track which values we've seen at each sequence length

Output

Length of shortest impossible sequence

Key Takeaway

🎯 Key Insight: Use greedy approach to track when all dice values have been seen at each sequence length

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use a greedy approach to track when we've seen all possible dice values. The optimal solution uses a set to track unseen values, incrementing the sequence length whenever all values have been seen. Time: O(n), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Build Missing Sequence	O(n)	O(k)	Greedily construct the shortest impossible sequence by tracking missing values
Brute Force - Check All Sequences	O(k^L × n × L)	O(L)	Generate all possible sequences and check if they exist as subsequences

Greedy - Build Missing Sequence — Algorithm Steps

Initialize a set to track unseen values (1 to k)
Iterate through rolls, removing seen values from the set
When set becomes empty, increment sequence length and reset set
Continue until we have processed all rolls
Return the final sequence length

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with unseen = {1,2,3,4}, length = 1

Process Rolls

Remove seen values from unseen set

Reset When Empty

When unseen is empty, increment length and reset

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int* rolls, int rollsLen, int k) {
    bool* unseen = (bool*)malloc((k + 1) * sizeof(bool));
    for (int i = 1; i <= k; i++) {
        unseen[i] = true;
    }
    int length = 1;
    int unseenCount = k;
    
    for (int i = 0; i < rollsLen; i++) {
        if (unseen[rolls[i]]) {
            unseen[rolls[i]] = false;
            unseenCount--;
            if (unseenCount == 0) {
                length++;
                for (int j = 1; j <= k; j++) {
                    unseen[j] = true;
                }
                unseenCount = k;
            }
        }
    }
    
    free(unseen);
    return length;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int rolls[1000];
    int rollsLen = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        rolls[rollsLen++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(rolls, rollsLen, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the rolls array

✓ Linear Growth

Space Complexity

O(k)

Set to track unseen values, maximum size k

✓ Linear Space

12.0K Views

Medium Frequency

~25 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Build Missing Sequence — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler