Shortest impossible sequence of rolls

Array Hash Table Greedy

69.3% acceptance

Feb 25, 2026

668

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashSet;


impl Solution {
  pub fn shortest_sequence(rolls: Vec<i32>, k: i32) -> i32 {
    let k = k as usize;
    let mut seen: HashSet<i32> = HashSet::new();
    let mut count = 1;
    for r in rolls {
      seen.insert(r);
      if seen.len() == k {
        count += 1;
        seen.clear();
      }
    }
    count
  }
}