AlgoMaster Logo

Time Needed to Buy Tickets

easyFrequency5 min readUpdated June 23, 2026

Understanding the Problem

We have a queue of people, each wanting to buy a certain number of tickets. The process works like a round-robin: each person at the front buys one ticket (taking 1 second), then goes to the back of the line if they still need more. Once someone has bought all their tickets, they leave the queue entirely.

We need to find how many seconds pass before the person at index k finishes buying all their tickets.

We do not have to simulate the entire queue. The time each person contributes depends only on their position relative to person k and how their ticket count compares to person k's, which leads to a single-pass formula.

Key Constraints:

  • 1 <= n <= 100 and 1 <= tickets[i] <= 100 → The total number of buy operations is at most sum(tickets), which is bounded by 100 * 100 = 10,000. A direct second-by-second simulation runs comfortably within these bounds.
  • 0 <= k < n → k is always a valid index, so there is no empty-input or out-of-range case to guard against.

Approach 1: Queue Simulation

Intuition

Do exactly what the problem describes. Maintain a queue, let each person at the front buy one ticket, decrement their count, and send them to the back if they still need more. Count each second as it passes. When person k's ticket count reaches zero, return the total time.

This models the round-robin process step by step. The code mirrors the problem statement directly, so its correctness is easy to confirm.

Algorithm

  1. Create a queue of (index, tickets remaining) pairs, initialized from the input array.
  2. Initialize a time counter to 0.
  3. While the queue is not empty:
    • Dequeue the front person.
    • Increment time by 1.
    • Decrement their ticket count by 1.
    • If this person is person k and their count is now 0, return time.
    • If their count is still greater than 0, enqueue them at the back.

Example Walkthrough

queue
1Initial queue: [index, ticketsRemaining]. Person k=2 needs 2 tickets.
Front
[0,2]
[1,3]
[2,2]
Rear
time
1Time counter starts at 0
0
1/7

Code

The simulation steps through every second, but each person's total contribution can be computed directly from the array. The next approach replaces the simulation with a single pass.

Approach 2: Single Pass (Optimal)

Intuition

Rather than simulating the queue round by round, compute how much time each person contributes before person k finishes.

Person k needs tickets[k] tickets, so the queue cycles through at most tickets[k] rounds (some people drop out earlier). Each person's contribution depends on their position relative to k:

  • People at or before index k (positions 0 through k): They buy in the same round as person k, including the final round. They contribute min(tickets[i], tickets[k]) seconds each. If they need fewer tickets than person k, they buy all of theirs and leave; if they need more, they buy exactly tickets[k] before person k finishes.
  • People after index k (positions k+1 through n-1): They buy after person k in each round. When person k buys their last ticket and stops, these people have not had their turn in that round. They participate in one fewer round, contributing min(tickets[i], tickets[k] - 1) seconds each.

Summing these contributions in one pass gives the answer.

Algorithm

  1. Initialize time = 0.
  2. For each person i from 0 to n-1:
    • If i <= k, add min(tickets[i], tickets[k]) to time.
    • If i > k, add min(tickets[i], tickets[k] - 1) to time.
  3. Return time.

Example Walkthrough

tickets
1tickets = [2, 3, 2], k = 2, tickets[k] = 2. Calculate each person's contribution.
0
2
1
3
2
2
k
time
1Running total starts at 0
0
1/5

Code