Time Needed to Buy Tickets

EasyQueue · Simulation · Counting🧩 Queue & Monotonic Deque LeetCode #2073 ↗Updated Oct 30, 2026

Problem

People stand in a line; person i wants tickets[i] tickets. Each second, the person at the front buys one ticket, then walks to the back of the line if they still need more (otherwise they leave). Return how many seconds pass until the person at index k has bought all of their tickets.

Inputtickets=[2,3,2], k=2Output6

Inputtickets=[5,1,1,1], k=0Output8

1 ≤ n ≤ 100 · 1 ≤ tickets[i] ≤ 100 · 0 ≤ k < n

Try it yourself

Java

class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Person k finishes in round tickets[k]. Everyone ahead of k buys at most tickets[k] tickets by then, everyone behind at most tickets[k] - 1 — so the answer is a single sum of mins.

PatternQueue & Monotonic Deque

Instinct Arrival order matters, or you need the max/min of a moving window - reach for a FIFO queue, or a deque of indices kept in sorted order.

Memory hack Old ones leave by the front door, weak ones get bounced out the back - so whoever stands at the front is always the champion.

Open the Queue & Monotonic Deque guide →

Approaches

Brute ForceSimulate the Queue

Time O(n · max(tickets))Space O(n)

Model the line literally: a queue of person indices. Each second, poll the front, decrement their count, and re-enqueue them if they still need tickets. Stop the moment person k reaches zero.

Java

public int timeRequiredToBuy(int[] tickets, int k) {
    int[] left = tickets.clone();
    Deque<Integer> line = new ArrayDeque<>();
    for (int i = 0; i < left.length; i++) line.offerLast(i);
    int time = 0;
    while (true) {
        int person = line.pollFirst();
        left[person]--;
        time++;
        if (left[person] == 0) {
            if (person == k) return time;
        } else {
            line.offerLast(person); // back of the line
        }
    }
}

Mirrors the statement exactly, but runs one step per ticket sold.

OptimalOne-Pass Counting

Time O(n)Space O(1)

Count each person's purchases up to the moment k finishes. People at index ≤ k get a turn in round tickets[k] before k is done, so they buy min(tickets[i], tickets[k]); people behind k miss that last round and buy min(tickets[i], tickets[k] - 1).

Java

public int timeRequiredToBuy(int[] tickets, int k) {
    int time = 0;
    for (int i = 0; i < tickets.length; i++) {
        // people behind k do not get a turn in k's final round
        int cap = i <= k ? tickets[k] : tickets[k] - 1;
        time += Math.min(tickets[i], cap);
    }
    return time;
}

Dry runtickets=[2,3,2], k=2

i personk target changed

start
5
k
1

1

1

cap ahead=5, behind=4
i=0
5
i k
1

1

1

+min(5,5)=5
i=1
5

1
i
1

1

+min(1,4)=1 → 6
i=2
5

1

1
i
1

+min(1,4)=1 → 7
i=3
5

1

1

1
i
+min(1,4)=1 → 8 ✔

Single pass, no simulation — the expected answer.

Pro tip

Explain the cap with rounds: in k's last round, only people in front of k (and k) get served.

At a glance

Level	Approach	Time	Space
Brute Force	Simulate the Queue	`O(n · max(tickets))`	`O(n)`
Optimal	One-Pass Counting	`O(n)`	`O(1)`

Common pitfalls

Using tickets[k] as the cap for people behind k — off by one per person.
Mutating the caller's tickets array in the simulation.
Stopping the simulation when anyone hits zero instead of person k.

Interview tips

Start with the queue simulation — it is quick and proves you read the rules.
Then reason in rounds to derive the min-sum formula.
Verify the formula on the [5,1,1,1], k=0 example.

Pattern

Round-robin queue → closed-form count → when each round serves everyone once, count per-person turns instead of simulating.

My notes saved in this browser