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.
This approach simulates the process of each person buying their tickets. We keep track of the time spent and decrement the ticket count from each person one at a time until the k-th person has purchased all their tickets.
We continuously loop through the array, simulating each person buying one ticket at a time if they have tickets remaining. We check after each purchase if the target person (k-th) has finished buying their tickets.
Time Complexity: O(n * max(tickets)) where max(tickets) is the maximum tickets any person wants to buy.
Space Complexity: O(1)
This approach avoids the simulation by calculating the total time taken mathematically. For this, we traverse through each person and calculate the time based on the number of people in the queue and the minimum value between their current tickets and the tickets needed by k-th person.
This solution avoids direct simulation by calculating how many tickets each person can buy based on their position relative to k.
Time Complexity: O(n)
Space Complexity: O(1)
According to the problem description, when the k^{th} person finishes buying tickets, all the people in front of the k^{th} person will not buy more tickets than the k^{th} person, and all the people behind the k^{th} person will not buy more tickets than the k^{th} person minus 1.
Therefore, we can traverse the entire queue. For the i^{th} person, if i leq k, the time to buy tickets is min(tickets[i], tickets[k]); otherwise, the time to buy tickets is min(tickets[i], tickets[k] - 1). We sum the buying time for all people to get the result.
The time complexity is O(n), where n is the length of the queue. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Simulation Approach | Time Complexity: O(n * max(tickets)) where max(tickets) is the maximum tickets any person wants to buy. |
| Mathematical Reduction Approach | Time Complexity: O(n) |
| Single Pass | — |
| 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 |
Time Needed to Buy Tickets - Leetcode 2073 - Python • NeetCodeIO • 19,310 views views
Watch 9 more video solutions →Practice Time Needed to Buy Tickets with our built-in code editor and test cases.
Practice on FleetCode