Time Needed to Buy Tickets

Difficulty: Easy | Acceptance: 72.50% | Paid: No Topics: Array, Queue, Simulation

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 ith person wants to buy tickets[i] tickets.

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 at position k (0-indexed) to finish buying all tickets.

• Examples
• Constraints
• Approach 1: Simulation using Queue
• Approach 2: Mathematical Calculation

Examples

Example 1:

Input: tickets = [2,3,2], k = 2
Output: 6
Explanation: 
- In the first pass, everyone in the line buys a ticket and the line becomes [1, 2, 1].
- In the second pass, everyone in the line buys a ticket and the line becomes [0, 1, 0].
The person at index 2 has successfully bought 2 tickets and finished.

Example 2:

Input: tickets = [5,1,1,1], k = 0
Output: 8
Explanation:
- In the first pass, everyone in the line buys a ticket and the line becomes [4, 0, 0, 0].
- In the next 4 passes, only the person in position 0 is buying tickets.
The person at index 0 has successfully bought 5 tickets and finished.

Constraints

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

Approach 1: Simulation using Queue

Intuition We can simulate the exact process described in the problem using a queue. We store the indices of people in the queue. We process the person at the front, decrement their ticket count, and if they still need tickets, we move them to the back. We stop when the person at index k has no tickets left.

Steps

• Initialize a queue with indices from 0 to n-1.
• Initialize a time counter to 0.
• While the queue is not empty:
  • Pop the front index i.
  • Decrement tickets[i] by 1.
  • Increment time by 1.
  • If tickets[i] is 0:
    • If i is equal to k, return the time.
  • Else:
    • Push i to the back of the queue.

from collections import deque
from typing import List

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        q = deque(range(len(tickets)))
        time = 0
        
        while q:
            i = q.popleft()
            tickets[i] -= 1
            time += 1
            
            if tickets[i] == 0:
                if i == k:
                    return time
            else:
                q.append(i)
                
        return time

Complexity

• Time: O(n * max(tickets)) - In the worst case, we iterate through the queue until the maximum number of tickets is bought.
• Space: O(n) - To store the queue.
• Notes: Straightforward simulation but can be optimized mathematically.

Approach 2: Mathematical Calculation

Intuition We can calculate the time directly without simulation. Every person i will buy at most tickets[k] tickets. However, if a person is behind k (i.e., i > k), they get one fewer turn because the person at k leaves the line before the person behind them can get their next ticket.

Steps

• Initialize time to 0.
• Iterate through the tickets array with index i and value t.
• If i <= k:
  • Add min(t, tickets[k]) to time.
• If i > k:
  • Add min(t, tickets[k] - 1) to time.
• Return time.

from typing import List

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

Complexity

• Time: O(n) - Single pass through the array.
• Space: O(1) - No extra space used besides variables.
• Notes: This is the most optimal solution.