Watch 10 video solutions for Time Needed to Buy Tickets, a easy level problem involving Array, Queue, Simulation. This walkthrough by NeetCodeIO has 19,310 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n people in a line queuing to buy tickets, where the 0th person is at the front of the line and the (n - 1)th person is at the back of the line.
You are given a 0-indexed integer array tickets of length n where the number of tickets that the ith person would like to buy is tickets[i].
Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.
Return the time taken for the person initially at position k (0-indexed) to finish buying tickets.
Example 1:
Input: tickets = [2,3,2], k = 2
Output: 6
Explanation:
Example 2:
Input: tickets = [5,1,1,1], k = 0
Output: 8
Explanation:
Constraints:
n == tickets.length1 <= n <= 1001 <= tickets[i] <= 1000 <= k < nProblem Overview: An array tickets represents how many tickets each person in a queue wants to buy. Each second, the person at the front buys one ticket and moves to the back if they still need more. The process stops when the person at index k finishes buying all their tickets. The goal is to compute the total time required.
Approach 1: Simulation with Queue (Time: O(sum(tickets)), Space: O(n))
This approach directly models the queue behavior. Push each person’s index and remaining ticket count into a queue and simulate the process second by second. At every step, pop the front person, decrement their ticket count, and if they still need tickets push them back to the queue. Stop once the person at index k buys their final ticket. The logic mirrors the real-world process and is easy to reason about. However, the loop may run up to sum(tickets) iterations in the worst case, which can be large if many people want many tickets. This method primarily uses a queue for ordering and simple simulation of events.
Approach 2: Mathematical Reduction (Time: O(n), Space: O(1))
The queue behavior has a predictable pattern that allows counting the time without simulating every second. Each person before or at index k can buy at most tickets[k] tickets before k finishes. Each person after k can buy at most tickets[k] - 1 tickets, because the process stops immediately after k purchases their last ticket. Iterate once through the array and accumulate contributions using min(tickets[i], tickets[k]) for i ≤ k and min(tickets[i], tickets[k] - 1) for i > k. This counts exactly how many seconds each person participates in the buying cycle. The solution runs in linear time with constant space and relies only on simple array iteration.
Recommended for interviews: Start by describing the simulation since it demonstrates understanding of the queue process and matches the problem statement directly. Then optimize to the mathematical counting approach. Interviewers typically expect the O(n) reduction because it removes unnecessary simulation and shows you recognized the purchase pattern across the queue.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Queue Simulation | O(sum(tickets)) | O(n) | When you want a direct model of the process or when explaining the logic step-by-step in interviews |
| Mathematical Reduction | O(n) | O(1) | Best for production or interview optimization since it counts contributions without simulating each second |