DSA problem
Time Needed to Buy Tickets
There are n people standing in a queue numbered 0 to n - 1, and the array tickets of length n describes how many tickets each person wants to buy. The line moves one person at a time: the person at the front of the line buys exactly one ticket, taking exactly one second, then if they still need more tickets they move to the back of the line; otherwise they leave. You are given an integer k, the 0-indexed position of a specific person in the original queue, and must return the number of seconds it takes for that person at index k to finish purchasing all of their tickets.
A direct simulation with an actual FIFO queue of indices is easy to write and runs in O(sum(tickets)) time. That is acceptable for the given constraints but is slower than necessary, because the strict round-robin behavior allows a closed-form count.
The key observation is that by the time person k is done, they have bought exactly tickets[k] tickets. Every other person i has bought as many tickets as they could, but bounded by how many rounds were available to them before person k finished. Specifically, person i at index i <= k participates in the same round that person k finishes in, so they buy min(tickets[i], tickets[k]) tickets. Person i at index i > k has one fewer chance, so they buy min(tickets[i], tickets[k] - 1) tickets.
Summing these contributions yields the total number of seconds in a single O(n) pass with O(1) extra space. The queue simulation is a great way to build intuition for the round-robin structure, and the closed-form formula is the optimal answer to implement in production code.
Examples
tickets = [2,3,2], k = 26tickets = [5,1,1,1], k = 08tickets = [84,49,5,24,70,77,87,8], k = 3154Constraints
- n == tickets.length
- 1 <= n <= 100
- 1 <= tickets[i] <= 100
- 0 <= k < n
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.