#2073

Easy

auto_awesomeQueue-driven state processing

LeetCode Problem Workspace

Time Needed to Buy Tickets

Calculate the total time for a specific person to buy all their tickets using queue-driven state processing.

Problem Statement

You are given a line of n people waiting to buy tickets, represented by an array tickets where tickets[i] is the number of tickets the ith person wants. Each person can only buy one ticket per second and must return to the end of the line if they have more tickets to buy.

Given an index k, compute how many seconds it takes for the person at position k to buy all their tickets. People with zero tickets left leave the line immediately, and the process continues until the target person completes their purchases.

Examples

Example 1

Input: tickets = [2,3,2], k = 2

Output: 6

Example 2

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

Output: 8

Constraints

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

Solution Approach

Simulate the Queue Directly

Loop through the tickets array repeatedly, decrementing one ticket per person per turn and adding one second each iteration. Stop counting when the person at index k has no tickets left. This mirrors the exact queue-driven state processing pattern of the problem.

Optimize with Minimum Ticket Cap

Instead of moving through the entire array each round, track the remaining tickets and count seconds by comparing each person's tickets to the target's. Only add seconds for people who still require tickets, reducing unnecessary simulation steps.

Single Pass Counting

Calculate the time by summing the minimum between each person's tickets and the target's tickets. If a person is before or at the target index, add the full minimum; if after, add only if their tickets exceed remaining rounds. This achieves O(n) time using the queue-driven logic without explicit rotation.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each person is processed once per effective ticket purchase up to the target's completion. Space complexity is O(1) since only counters are maintained, not a full queue.

What Interviewers Usually Probe

Ask if you can avoid simulating the entire queue each second.
Check if you understand how returning to the end of the line affects total time.
Notice opportunities to optimize using comparisons with the target person's tickets.

Common Pitfalls or Variants

Common pitfalls

Forgetting that each person buys only one ticket per turn and must rejoin the line.
Counting extra seconds after the target person has finished buying all tickets.
Misindexing when calculating time for people behind the target in the queue.

Follow-up variants

Change the queue to allow multiple tickets per second and compute total time accordingly.
Consider dynamic arrival where new people join the line, affecting queue-driven timing.
Modify the problem to find total time for multiple target indices simultaneously.

FAQ

What is the best approach to solve Time Needed to Buy Tickets efficiently?

Simulate the queue or use single-pass counting with the minimum of each person's tickets and the target's tickets, following the queue-driven pattern.

Can this problem be solved without explicitly rotating the array?

Yes, by summing contributions per person based on remaining tickets relative to the target index, you can avoid full simulation.

How do you handle people behind the target in the queue?

Only count their turns if they have tickets remaining when the target person has not finished buying all tickets.

What is the time and space complexity of this approach?

Time complexity is O(n) and space complexity is O(1), since we only use counters and no extra arrays or queues.

Why is this problem considered a queue-driven state processing pattern?

Because each person’s position and ticket count directly determine the sequence of actions, mirroring real queue movement and state changes.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        ans = 0
        for i, x in enumerate(tickets):
            ans += min(x, tickets[k] if i <= k else tickets[k] - 1)
        return ans

Continue Practicing

#1823 find the winner of the circular game #1700 number of students unable to eat lunch #2071 maximum number of tasks you can assign