2350. Shortest Impossible Sequence of Rolls LeetCode Solution

In this guide, you will get 2350. Shortest Impossible Sequence of Rolls LeetCode Solution with the best time and space complexity. The solution to Shortest Impossible Sequence of Rolls problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Shortest Impossible Sequence of Rolls solution in C++
4. Shortest Impossible Sequence of Rolls solution in Java
5. Shortest Impossible Sequence of Rolls solution in Python
6. Additional Resources

Problem Statement of Shortest Impossible Sequence of Rolls

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(k)

2350. Shortest Impossible Sequence of Rolls LeetCode Solution in C++

class Solution {
 public:
  int shortestSequence(vector<int>& rolls, int k) {
    int ans = 1;  // the the next target length
    unordered_set<int> seen;

    for (const int roll : rolls) {
      seen.insert(roll);
      if (seen.size() == k) {
        // Have all combinations that form `ans` length, and we are going to
        // extend the sequence to `ans + 1` length.
        ++ans;
        seen.clear();
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2350. Shortest Impossible Sequence of Rolls LeetCode Solution in Java

class Solution {
  public int shortestSequence(int[] rolls, int k) {
    int ans = 1; // the the next target length
    Set<Integer> seen = new HashSet<>();

    for (final int roll : rolls) {
      seen.add(roll);
      if (seen.size() == k) {
        // Have all combinations that form `ans` length, and we are going to
        // extend the sequence to `ans + 1` length.
        ++ans;
        seen.clear();
      }
    }

    return ans;
  }
}
// code provided by PROGIEZ

2350. Shortest Impossible Sequence of Rolls LeetCode Solution in Python

class Solution:
  def shortestSequence(self, rolls: list[int], k: int) -> int:
    ans = 1  # the the next target length
    seen = set()

    for roll in rolls:
      seen.add(roll)
      if len(seen) == k:
        # Have all combinations that form `ans` length, and we are going to
        # extend the sequence to `ans + 1` length.
        ans += 1
        seen.clear()

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.