Time Needed to Buy Tickets
Easy · Stack & Strings · Array · Queue · Simulation
Problem
n people stand in a queue, and person i (0-indexed from the front) wants to buy tickets[i] tickets. Buying one ticket takes exactly one second, and a person can buy only one ticket per turn.
After buying a ticket, a person who still needs more goes straight to the back of the line (instantly). A person who has all their tickets leaves the line.
Return how many seconds pass until the person at position k has bought all of their tickets.
Examples
Input: tickets = [3,1,2], k = 2 Output: 5
Purchases go 0, 1, 2, then 0, 2: person 2 buys their last ticket at second 5.
Input: tickets = [4,2,5], k = 0 Output: 9
Person 0 buys 4, person 1 buys 2 and person 2 buys 3 before person 0's fourth ticket is done: 9 seconds.
Input: tickets = [1], k = 0 Output: 1
One person, one ticket.
Constraints
- n == len(tickets)
- 1 <= n <= 100
- 1 <= tickets[i] <= 100
- 0 <= k < n
Approaches
- Baseline: simulate the queue — time O(n · max(tickets)), space O(n)
Follow-up
With 10^5 people wanting up to 10^9 tickets each, the simulation is out of reach, but the one-pass count is still instant. The use cases ask for every person's finishing time at once and for who buys the m-th ticket, both of which use the same "after r full rounds each person has bought min(tickets[i], r)" idea.
Related problems
Start free on Cariara · Coding problems · System design studio
