#2073 Time Needed to Buy Tickets
the problem
In plain words
People stand in a line; person i wants tickets[i] tickets. Each second the front person buys one ticket and, if they still need more, goes to the back of the line. How many seconds until person k has all their tickets?
in tickets = [2,3,2], k = 2
out 6
in tickets = [5,1,1,1], k = 0
out 8
- 1 ≤ n ≤ 100
- 1 ≤ tickets[i] ≤ 100
- 0 ≤ k < n
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternMath shortcut (closed form)Simulation
Person k needs tickets[k] rounds. Everyone at or before k buys in each of those rounds (if they still need tickets); everyone after k misses the last round, because k finishes first.
solutions
From brute force to optimal
Literally run the process: poll the front, sell one ticket, offer them back if they need more.
- Queue all indices.
- Each second: poll, decrement, time++.
- Stop when person k reaches 0; otherwise offer back if they still need tickets.
One loop iteration per ticket sold — at most n · max(tickets).
The queue and a copy of tickets.
class Solution { public int timeRequiredToBuy(int[] tickets, int k) { int[] left = tickets.clone(); Queue<Integer> line = new ArrayDeque<>(); // people, by index for (int i = 0; i < left.length; i++) line.offer(i); int time = 0; while (true) { int person = line.poll(); // front person buys one ticket left[person]--; time++; if (person == k && left[person] == 0) return time; if (left[person] > 0) line.offer(person); // back of the line } }}Add min(tickets[i], tickets[k]) for i ≤ k and min(tickets[i], tickets[k] − 1) for i > k.
- For i ≤ k: they buy in each of k's rounds, up to their own need.
- For i > k: they get one round fewer.
- Sum it up.
One pass over the line.
A single counter.
class Solution { public int timeRequiredToBuy(int[] tickets, int k) { int time = 0; for (int i = 0; i < tickets.length; i++) { if (i <= k) time += Math.min(tickets[i], tickets[k]); // at or ahead of k: up to tickets[k] rounds else time += Math.min(tickets[i], tickets[k] - 1); // behind k: k is done before their last round } return time; }}in the room
How to say it in the interview
talk track
- Give the simulation first — it's correct and easy. Then derive the formula from "how many tickets does each person buy before k is done?"
traps
- Giving people after k a full
tickets[k]rounds — k leaves before they get the last one.
what they ask next
Follow-ups
What if tickets[i] could be up to 10⁹?
The simulation is then far too slow (one step per ticket sold). The formula is still one O(n) pass — just add into a long, since the total can pass 2³¹ − 1.
How slow is the simulation at these limits?
At most n × max(tickets) = 100 × 100 = 10⁴ steps, so it passes here. The formula matters once ticket counts grow.
before you submit
Edge cases to test
- Person k is first and needs one ticket → the answer is 1.
- Person k is last in line: everyone ahead buys up to
tickets[k]tickets. - People who need fewer tickets leave early and stop costing time.
practise next
Similar problems
- #950Reveal Cards In Increasing OrderMediumin Queues
- #933Number of Recent CallsEasyin Queues