Time Needed to Buy Tickets — Solution in Python, Java & C++
Time Needed to Buy Tickets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Time Needed to Buy Tickets is an easy coding problem on arrays, simulation and queue, asked in Amazon, Adobe and Twitter interviews.
- Difficulty: Easy
- Topics: Arrays, Simulation, Queue
- Asked at: Amazon, Adobe, Twitter
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
People stand in a queue; tickets[i] is the number of tickets person i still wants. Buying one ticket takes exactly one second. After buying one ticket a person goes to the back of the queue, unless they are done, in which case they leave.
Return the number of seconds it takes the person at position k to buy all of their tickets.
Example 1
Input: tickets = [2,3,2], k = 2
Output: 6
Example 2
Input: tickets = [5,1,1,1], k = 0
Output: 8
Example 3
Input: tickets = [1], k = 0
Output: 1
Constraints
1 <= tickets.length <= 401 <= tickets[i] <= 1000 <= k < tickets.length
Hints for Time Needed to Buy Tickets
Hint 1
Simulating the queue works, but each person's contribution can be counted directly.
Hint 2
Someone at or before
kbuys at mosttickets[k]tickets before personkfinishes.Hint 3
Someone after
kgets one fewer round, so they contribute at mosttickets[k] - 1.
How to solve Time Needed to Buy Tickets
Count each person's contribution directly: someone at or before k buys at most tickets[k] before k finishes, someone after k at most tickets[k] - 1.
Approach
- Sum
min(tickets[i], tickets[k])fori <= kandmin(tickets[i], tickets[k] - 1)fori > k.
Why it works
Person k finishes during their tickets[k]-th round; everyone ahead has had exactly that many turns, everyone behind one fewer.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Simulating the queue is also correct but
O(n · max(tickets)).
Reference solution
Python
def timeRequiredToBuy(tickets, k: int) -> int:
time = 0
for i, want in enumerate(tickets):
if i <= k:
time += min(want, tickets[k])
else:
time += min(want, tickets[k] - 1)
return timeJava
public static 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]);
else time += Math.min(tickets[i], tickets[k] - 1);
}
return time;
}C++
int timeRequiredToBuy(vector<int>& tickets, int k) {
int time = 0;
for (int i = 0; i < (int) tickets.size(); i++) {
if (i <= k) time += min(tickets[i], tickets[k]);
else time += min(tickets[i], tickets[k] - 1);
}
return time;
}JavaScript
var timeRequiredToBuy = function(tickets, k) {
let time = 0;
for (let i = 0; i < tickets.length; i++) {
if (i <= k) time += Math.min(tickets[i], tickets[k]);
else time += Math.min(tickets[i], tickets[k] - 1);
}
return time;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Queues and Deques