AlgoMaster Logo

Time Needed to Buy Tickets

Last Updated: March 29, 2026

easy
3 min read

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 figure out exactly how many seconds pass before the person at index k finishes buying all their tickets.

The key insight here is that we do not actually need to simulate the entire queue. We can figure out how much time each person contributes to the total wait by thinking about their position relative to person k and how many tickets they need compared to person k.

Key Constraints:

  • 1 <= n <= 100 → The array is tiny. Even an O(n^2) simulation with nested loops runs in at most 10,000 operations, which is instant.
  • 1 <= tickets[i] <= 100 → Each person wants at most 100 tickets. Combined with n <= 100, the total simulation steps are at most 10,000.
  • 0 <= k < n → k is always a valid index. Given these small constraints, even a direct simulation is perfectly fine, but there is a clean O(n) mathematical approach worth learning.

Approach 1: Queue Simulation

Intuition

The most straightforward way to solve this is to 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 hits zero, return the total time.

This is essentially modeling the round-robin process step by step. It is easy to reason about correctness because the code mirrors the problem statement directly.

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

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

Code

This approach works correctly but simulates every single second of the process. Most of the simulation is predictable. Can we calculate each person's contribution directly, without simulating the queue at all?

Approach 2: Single Pass (Optimal)

Intuition

Instead of simulating the queue round by round, let's think mathematically about how much time each person contributes before person k finishes.

Person k needs tickets[k] tickets. So the queue will cycle through at most tickets[k] full rounds (though some people drop out earlier). Here is the key observation:

  • People at or before index k (positions 0 through k): They get to buy a ticket in the same round as person k. So 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] tickets before person k finishes.
  • People after index k (positions k+1 through n-1): They buy their ticket after person k in each round. So in the final round (when person k buys their last ticket), these people have not had their turn yet. They participate in one fewer round, contributing min(tickets[i], tickets[k] - 1) seconds each.

That is the entire solution. One pass through the array, summing up each person's contribution.

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

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

Code