Is Time Needed to Buy Tickets easy or hard?

LeetCode classifies Time Needed to Buy Tickets as an Easy problem with an acceptance rate above 70%. The simulation idea is straightforward, while the O(n) optimization introduces a small counting insight.

Time Needed to Buy Tickets Python/Java solution

Both Python and Java implementations typically follow the O(n) counting strategy. Iterate through the array, apply the min(tickets[i], tickets[k]) or min(tickets[i], tickets[k]-1) rule depending on the index, and sum the results to compute the total time.

How to solve Time Needed to Buy Tickets in O(n)?

Iterate through the tickets array and accumulate how many times each person contributes to the buying process. For indices i ≤ k add min(tickets[i], tickets[k]). For indices i > k add min(tickets[i], tickets[k] - 1). The sum of these values gives the total time.

What is the best approach for Time Needed to Buy Tickets?

The mathematical reduction approach is the most efficient. Instead of simulating the queue second by second, it counts how many times each person gets a chance to buy before person k finishes. This reduces the complexity to O(n) time and O(1) space.

Is Time Needed to Buy Tickets asked at Google/Amazon/Meta?

Queue and simulation problems like this commonly appear in interviews at companies such as Amazon and Google. The question tests reasoning about queue behavior, counting patterns, and the ability to optimize a simulation into a mathematical solution.

What data structure is used in Time Needed to Buy Tickets?

The direct approach uses a queue to simulate people cycling through the ticket line. The optimized solution does not require additional data structures and instead relies on simple array iteration and counting.

What is the time complexity of Time Needed to Buy Tickets?

The optimal solution runs in O(n) time and O(1) space by iterating through the array once and counting how many tickets each person can buy before index k completes their purchases. A straightforward simulation approach takes O(sum(tickets)) time.

Description Hints 2 Solution Video 12:45

2073. Time Needed to Buy Tickets

Easy73.5% acceptance7 companies

There are n people in a line queuing to buy tickets, where the 0^th 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 i^th 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:

The queue starts as [2,3,2], where the kth person is underlined.
After the person at the front has bought a ticket, the queue becomes [3,2,1] at 1 second.
Continuing this process, the queue becomes [2,1,2] at 2 seconds.
Continuing this process, the queue becomes [1,2,1] at 3 seconds.
Continuing this process, the queue becomes [2,1] at 4 seconds. Note: the person at the front left the queue.
Continuing this process, the queue becomes [1,1] at 5 seconds.
Continuing this process, the queue becomes [1] at 6 seconds. The kth person has bought all their tickets, so return 6.

Example 2:

Input: tickets = [5,1,1,1], k = 0

Output: 8

Explanation:

The queue starts as [5,1,1,1], where the kth person is underlined.
After the person at the front has bought a ticket, the queue becomes [1,1,1,4] at 1 second.
Continuing this process for 3 seconds, the queue becomes [4] at 4 seconds.
Continuing this process for 4 seconds, the queue becomes [] at 8 seconds. The kth person has bought all their tickets, so return 8.

Constraints:

n == tickets.length
1 <= n <= 100
1 <= tickets[i] <= 100
0 <= k < n

Asked at 7 companies

Twitter Innovaccer

Google Amazon Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Loop through the line of people and decrement the number of tickets for each to buy one at a time as if simulating the line moving forward. Keep track of how many tickets have been sold up until person k has no more tickets to buy.

Hint 2

Remember that those who have no more tickets to buy will leave the line.

12:45

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution