Shortest Impossible Sequence of Rolls

leetcode 2350. Shortest Impossible Sequence of Rolls

Intuition

Define round to be some sort of range, all numbers form 1 to k is found in this round. Loop through rolls, try to find the last round, and answer is round+1. So, we use stack to ignore possible duplicate numbers, and if stack.size() == k , we know we find all the numbers. Therefore, we clear the stack, and go to another round.

Code

int shortestSequence(vector<int>& rolls, int k) {
	unordered_set<int>st;
	int res = 1;
	for(auto& i : rolls) {
		st.insert(i);
		if(st.size() == k) {
			st.clear();
			res++;
		}
	}
	return res;
}

Complexity Analysis

Time: O(n)Space: O(n)