A column of shipping containers sits on a dock, described bottom-to-top by an array of positive integer labels. Dockworkers can only lift containers off the very top of the stack, one at a time, and each lift is logged as one removal. A shipment manifest requires recovering at least one container bearing each label from 1 through k before the crew can move on. Given the bottom-to-top label order and the integer k, compute the minimum number of top removals needed so that every label in 1..k has been removed at least once. It is guaranteed that each label from 1 to k appears somewhere in the stack.
Print a single integer: the minimum number of top removals required.
Example 1
Input
5 3 4 3 2 5 1
Expected
4
Explanation
Bottom-to-top the stack is [4,3,2,5,1], so removals proceed from the top: 1 (removal 1, collected {1}), 5 (removal 2, not needed since k=3), 2 (removal 3, collected {1,2}), 3 (removal 4, collected {1,2,3} -- done). The answer is 4.
Example 2
Input
5 5 4 3 2 5 1
Expected
5
Explanation
Now every label 1..5 is required. Label 4 sits at the very bottom of the stack (index 0), so the entire stack of 5 containers must be removed before it is recovered. The answer is 5.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →