We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Time Needed to Buy Tickets

Number: 2195

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Meta, X

Problem Description

There are n people in a queue to buy tickets. Each person i wants to buy tickets[i] number of tickets. Every second, the person at the front of the queue buys one ticket and if they still need more, they go to the back of the line instantaneously. If they have bought all the tickets they needed, they leave the queue. Given a position k (0-indexed) representing a person in the initial queue, return the total time taken for that person to finish buying all their tickets.

Key Insights

  • The problem simulates a round-robin process where every person buys one ticket per turn.
  • Instead of simulating the entire queue operation, it is possible to compute the time using counts of rounds each person goes through.
  • For each person, compare the number of tickets they need with the tickets needed by the kth person to determine if they buy a ticket in the final round.
  • The kth person might only receive as many turns as tickets[k] while others ahead or after might receive an extra turn if they still have tickets left when kth person finishes in the round.

Space and Time Complexity

Time Complexity: O(n) where n is the number of people in the queue. Space Complexity: O(1) as only constant extra space is used.

Solution

The idea is to count how many seconds (or turns) each person in the queue spends buying tickets. For every person i in the queue, the number of turns they get to buy a ticket is the minimum between their required tickets and tickets[k] (the kth person's tickets). However, for person i where the index is less than or equal to k, if they require exactly tickets[k] tickets, they get to buy a ticket in the final round; otherwise, if i is after k, they only get turns up to tickets[k] - 1 since the kth person finishes during the kth round.

This insight leads to a formula. The total time is the sum over all i of: min(tickets[i], tickets[k] - (i > k ? 1 : 0))

Using this, we avoid explicit simulation and compute the answer directly.

Code Solutions

# Function to calculate the time needed for kth person to finish buying tickets.
def time_required_to_buy(tickets, k):
    kth_tickets = tickets[k]
    time = 0
    # Loop over each person in the queue.
    for i, ticket in enumerate(tickets):
        # If the person is after kth, they only get up to kth_tickets - 1 turns.
        if i > k:
            time += min(ticket, kth_tickets - 1)
        else:
            time += min(ticket, kth_tickets)
    return time

# Example usage:
print(time_required_to_buy([2,3,2], 2))  # Expected output: 6
← Back to All Questions