Time Needed To Buy Tickets

Problem Summary

• Given a list of people who want to buy tickets in a queue. Calculate how many turns / seconds it would take for the person on $k^{th}$ index to buy all their tickets

Key Observations

• A person can buy 1 ticket at a time
• Buying once increments the time by 1 second

Approach Taken

• You can simulate the queue
• OR, do math to get to an answer in $O(n)$

Main Concepts Used

• Queue

Code (Simulation)

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        queue = deque()
        for index, ticketsNeeded in enumerate(tickets):
            queue.append((ticketsNeeded, index == k))

        time = 0
        while True:
            time += 1
            ticketRequired, isTracked = queue.popleft()

            if ticketRequired == 1 and isTracked:
                # the tracked person will buy their last ticket and get out of the queue
                return time
            elif ticketRequired != 1:
                queue.append((ticketRequired - 1, isTracked))

Time & Space Complexity

• Time: $O(n\ast T)$ → Reason: where $n$ is the number of people in line, and $T$ is the maximum number of tickets any person needs. This is because, in the worst case, we're decrementing the ticket needs up to $T$ times across all n people.
• Space: $O(n)$ → Reason: Storing a copy of the input for simulation

Code (Simulation - Improved)

• We can improve the code by improving the space complexity to $O(1)$ while keeping the time complexity the same

Code (Optimal)

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        result = 0
        for index, ticket in enumerate(tickets):
            if index <= k:
                # process people front of the person
                result += min(tickets[k], ticket)
            else:
                # process people after the person
                result += min(tickets[k] - 1, ticket)
        return result

Time & Space Complexity

• Time: $O(n)$ → Reason: One pass
• Space: $O(1)$ → Reason: Just storing result variable