Time Needed to Buy Tickets — Solution

Problem

A queue of people each want to buy some number of tickets. On every turn, the front person buys exactly one ticket and moves to the back of the line — or leaves if they've bought all they need. Each purchase takes exactly one second. Given the initial ticket counts and a target index k, return the total time until person k has bought all their tickets.

• Input: tickets = [2, 3, 2], k = 2
• Output: 6
• Explanation: After three seconds everyone has bought one ticket each; after three more seconds person 0 finishes and person 2 (our target) buys their second ticket and leaves.

Counter-example showing the asymmetry: with tickets = [5, 1, 1, 1] and k = 0, the three people behind person 0 each buy only 1 ticket before they're done (time 4), then person 0 buys 4 more alone — total 8, not 5.

Intuition

The queue is circular, so every person gets a turn in the same order each round. Person k needs tickets[k] full rounds. Everyone before k in the original order participates in all tickets[k] of those rounds (or fewer if they run out first). Everyone after k gets one fewer full round — they don't get a turn in the final cycle because person k finishes mid-round. This lets us compute the answer as a single sum without simulating anything.

Approach 1 — Simulation

Walk through the queue one person at a time, decrement their counter, and stop the moment person k reaches zero.

1. Loop until tickets[k] reaches zero.
2. In each pass, iterate through every person in order.
3. If the person still needs tickets, decrement their count and add one second to the timer.
4. Check immediately after decrementing — if tickets[k] just hit zero, return the timer.
5. Continue to the next person otherwise.

1def timeRequiredToBuy(tickets: list[int], k: int) -> int:
2    time = 0
3    while tickets[k] > 0:
4        for i in range(len(tickets)):
5            if tickets[i] > 0:
6                tickets[i] -= 1
7                time += 1
8            if tickets[k] == 0:  # person k just finished mid-round
9                return time
10    return time

Time: O(n × max(tickets)) — worst case is one full pass per ticket the target person needs.
Space: O(1) — only a counter, modifying the input array in-place.

Approach 2 — Math

Compute the answer directly by summing each person's contribution.

1. Record target = tickets[k] — the number of full rounds person k participates in.
2. For every person at index i ≤ k, add min(tickets[i], target) — they get a turn in each of k's rounds, capped by how many they actually need.
3. For every person at index i > k, add min(tickets[i], target - 1) — they get one fewer turn because k finishes before them in the final round.
4. Return the total.

1def timeRequiredToBuy(tickets: list[int], k: int) -> int:
2    target = tickets[k]
3    total_time = 0
4    for i, count in enumerate(tickets):
5        if i <= k:
6            total_time += min(count, target)
7        else:
8            # people behind k don't get a turn in the final round
9            total_time += min(count, target - 1)
10    return total_time

Time: O(n) — a single pass through the array.
Space: O(1) — no extra data structures.

Complexity Summary

Common Mistakes

• Forgetting the - 1 for people after k. Folks behind the target person never get their turn in the final round — using min(tickets[i], target) for all indices overcounts by one full round for each of them.
• Not stopping mid-round in the simulation. Breaking or returning only at the end of the inner for-loop counts extra seconds for people after k who technically hadn't gone yet when k finished.
• Skipping people with zero tickets in the simulation. Once a person's count hits zero they're out of the queue — forgetting the if tickets[i] > 0 guard increments time even for people who've already left.
• Using tickets[k] after simulating. If you mutate the array during simulation, tickets[k] becomes 0 before the math approach reads it — always snapshot target = tickets[k] first.
• Thinking all positions are symmetric. The split at index k isn't about distance from k; it's strictly about whether the person appears before or after k in the original ordering, because that determines who gets a turn before k exits.

Related Problems

• Gas Station — circular iteration where cumulative state determines the valid starting position
• Reveal Cards In Increasing Order — queue simulation where insertion order matters
• Daily Temperatures — computing wait-time until a future condition is met
• Sliding Window Maximum — deque-based queue manipulation for efficient window queries
• Rotate Array — circular array manipulation requiring careful index arithmetic