Skip to main content
Talentd

Time Needed to Buy Tickets - Solution & Explanation

EasyArrayQueueSimulation15 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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:

  • 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

Approach Overview

Problem 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 1: Simulation Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * max(tickets)) where max(tickets) is the maximum tickets any person wants to buy.
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Mathematical Reduction Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Single Pass

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Simulation Approach

Time Complexity: O(n * max(tickets)) where max(tickets) is the maximum tickets any person wants to buy.
Space Complexity: O(1)

Mathematical Reduction Approach

Time Complexity: O(n)
Space Complexity: O(1)

Single Pass—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Queue SimulationO(sum(tickets))O(n)When you want a direct model of the process or when explaining the logic step-by-step in interviews
Mathematical ReductionO(n)O(1)Best for production or interview optimization since it counts contributions without simulating each second

Video Solution

Time Needed to Buy Tickets - Leetcode 2073 - Python • NeetCodeIO • 20,097 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Time Needed to Buy Tickets with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Students Unable to Eat Lunch