2073. Time Needed to Buy Tickets

EasyQueueArraySimulation
Leetcode Link

Problem Description

In this problem, there are n individuals standing in a line to purchase tickets, with the queue arranged such that the 0th person is at the start of the line and the (n - 1)th person is at the end of the line. An array tickets of length n is provided, where each element tickets[i] denotes the number of tickets the ith person wishes to buy.

The purchase process is such that each person requires exactly 1 second to buy a single ticket, and can only buy one ticket at a time. After buying a ticket, if a person wants to buy more, they must go to the end of the line to purchase another ticket. This transition is assumed to be instantaneous. When an individual has no remaining tickets they wish to purchase, they leave the line.

The task is to calculate how much time it will take for the person in position k (using 0-based indexing) in the line to complete all their ticket purchases.

Intuition

To determine the total time required for the kth person to buy all their tickets, we have to simulate the ticket-buying process, respecting each person in the line. The main insights for the solution are:

  • Every person in the line, including person k, will buy tickets in rounds. In each round, every person, starting from the front of the line, will buy one ticket if they still want to purchase tickets and then go to the end of the line.

  • A person will leave the line as soon as they have no tickets left to buy.

  • The person at the kth position will buy their last ticket and leave the line, and will not go to the end of the line again.

Based on these points, the solution iterates over each person in the queue:

  • For people ahead of or at position k, the kth person will have to wait for each one of them to buy tickets up to the number of tickets person k wants (as both will get to buy their tickets). The minimum between tickets[k] (the number of tickets person k wants) and tickets[i] (the number of tickets the current person wants) is added to the total time.

  • For people behind position k, the kth person will wait for each one of them to buy tickets only up to one less than the number of tickets they want (because after the kth person buys their last ticket, they will leave and not wait for these people anymore). Hence, the minimum between tickets[k] - 1 (one less than the tickets k wants, because k won't buy a ticket after the final one) and tickets[i] is added to the total time.

The sum of all these minimums gives the total time taken for the person at position k to finish buying their tickets.

Learn more about Queue patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Solution Approach

The given solution follows a straightforward approach without the need for complex algorithms or data structures. The logic simply simulates the purchasing of tickets person by person. Here's a more detailed breakdown:

  • Initialize ans to zero, which will accumulate the total time required for the kth person to buy their tickets.

  • Loop through each person in the tickets array using enumerate, which provides both the index i and the number of tickets t that person wants.

    • For a person at or before the kth person in the queue (i <= k): Add the minimum of tickets[k] and t to ans. This represents the kth person waiting for each of the people in front of them, including themselves, to buy up to the same number of tickets that the kth person wants since they will all get to that number of tickets purchased before the kth person finishes.

    • For a person after the kth person in the queue (i > k): Add the minimum of tickets[k] - 1 and t to ans. This represents the kth person waiting for each of the people behind them to buy their tickets, but only up until the point just before k buys their last ticket. Since the kth person won't queue again after buying their last ticket, they won't wait for any tickets bought by the people behind them this final time around.

  • After the loop finishes, ans holds the total time taken for the person at position k to buy all their tickets, and that value is returned.

This solution ensures that the time the kth person will wait for others is correctly accounted for, adjusting for when they and the people in line ahead of them will buy tickets, and when they won't be in line anymore after buying their last ticket which is why they wait for one ticket less from those behind them. It's a clear and efficient way to simulate the queue process without the need for actual queue manipulation or any additional space, resulting in an O(n) time complexity where n is the number of people in the queue.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Example Walkthrough

Let's take a small example to illustrate the solution approach:

Suppose there are 5 individuals in a line (so n = 5) meaning to purchase tickets and their respective tickets are the number of tickets they want to buy represented by an array tickets = [1, 2, 5, 2, 1]. We want to find out how long it will take for the 3rd person (k = 2, 0-indexed) to buy all of their tickets.

Here is a step-by-step simulation following the solution approach:

  • Initialization: ans starts at 0.

  • First Pass (i = 0, t = 1, k = 2): The first person wants 1 ticket, which is less than what the 3rd person wants, so we add 1 to ans. ans = 1.

  • Second Pass (i = 1, t = 2, k = 2): The second person wants 2 tickets, which is less than what the 3rd person wants, so we add 2 to ans. ans = 1 + 2 = 3.

  • Third Pass (i = 2, t = 5, k = 2): The third person is the person in question, they want 5 tickets, so they will buy all their tickets. Add 5 to ans. ans = 3 + 5 = 8.

  • Fourth Pass (i = 3, t = 2, k = 2): The fourth person wants 2 tickets. Since the 3rd person will not queue after buying their fifth ticket, we add min(5 - 1, 2) to ans, which is 2. ans = 8 + 2 = 10.

  • Fifth Pass (i = 4, t = 1, k = 2): The fifth person wants 1 ticket, which is again less than what the 3rd person wants minus one, so we add 1 to ans. ans = 10 + 1 = 11.

After going through all individuals in the line:

  • For individuals ahead of or at position k (the 3rd person), we added the minimum of the number of tickets they want and the number of tickets the 3rd person wants to ans.

  • For individuals behind position k, we added the minimum of one less than the number of tickets the 3rd person wants and the number of tickets they want to ans.

The total time the 3rd person will wait is ans = 11. Hence, the 3rd person will take 11 seconds to buy all of their tickets.

Solution Implementation

1from typing import List
2
3class Solution:
4    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
5        # Initialize the total time required to 0
6        total_time = 0
7      
8        # Iterate over the ticket queue to simulate the time passing
9        for index, tickets_at_this_position in enumerate(tickets):
10            # If the current position is before or at the target position k
11            if index <= k:
12                # Add the minimum of the target tickets and tickets at the current position
13                # It ensures we do not count the extra tickets the target person doesn't need
14                total_time += min(tickets[k], tickets_at_this_position)
15            else:
16                # After the target person has bought their tickets, they will not buy more 
17                # Thus, for the people after the target, we consider one less ticket for the target
18                # Person at position k would have already bought their ticket when turn comes to later positions
19                total_time += min(tickets[k] - 1, tickets_at_this_position)
20      
21        # Return the calculated total time
22        return total_time
23
24# Example usage:
25# sol = Solution()
26# print(sol.timeRequiredToBuy([2, 3, 2], 2))  # This would output 6, the total time to buy tickets
27
1class Solution {
2
3    /**
4     * Calculate the time required for a person to buy tickets.
5     *
6     * @param tickets Array representing the number of tickets each person in the queue needs.
7     * @param k Index of the person whose time to buy tickets is being calculated.
8     * @return The time required for the person at index k to buy their tickets.
9     */
10    public int timeRequiredToBuy(int[] tickets, int k) {
11        // Initialize the answer variable to store the total time required.
12        int totalTime = 0;
13
14        // Loop through each person in the tickets array.
15        for (int i = 0; i < tickets.length; i++) {
16            // If the current person is before or at the position k in the queue,
17            // they will buy tickets[i] amount or the same amount as the person
18            // at the position k, whichever is smaller.
19            if (i <= k) {
20                totalTime += Math.min(tickets[k], tickets[i]);
21            } else {
22                // If the current person is after the position k in the queue,
23                // they can only buy till tickets[k] - 1 as the person at k
24                // will buy their last ticket before them.
25                totalTime += Math.min(tickets[k] - 1, tickets[i]);
26            }
27        }
28
29        // Return the total time required for the person at index k to buy their tickets.
30        return totalTime;
31    }
32}
33
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Calculates the time required to buy tickets
7    int timeRequiredToBuy(vector<int>& tickets, int k) {
8        int totalTime = 0; // Initialize the total time to 0
9        int n = tickets.size(); // Get the number of people in the line
10      
11        for (int i = 0; i < n; ++i) {
12            if (i <= k) {
13                // If the person is before or at position k, only buy until the 
14                // number of tickets the kth person needs
15                totalTime += min(tickets[k], tickets[i]);
16            } else {
17                // If the person is after the kth person, they can only buy until
18                // one less than the number of tickets the kth person needs, because
19                // when the kth gets their last ticket, these ones can't buy any more.
20                totalTime += min(tickets[k] - 1, tickets[i]);
21            }
22        }
23        return totalTime; // Return the total time calculated
24    }
25};
26
1function timeRequiredToBuy(tickets: number[], k: number): number {
2    const totalPeople = tickets.length;
3    let ticketsForTarget = tickets[k] - 1; // Subtract 1 because the target will purchase their last ticket in the end
4    let totalTime = 0; // Initialize the total time needed
5
6    // Round 1: Everyone purchases tickets up to the number of tickets the target person needs minus one
7    for (let i = 0; i < totalPeople; i++) {
8        if (tickets[i] <= ticketsForTarget) {
9            totalTime += tickets[i]; // Add the number of tickets each person can buy without exceeding target
10            tickets[i] = 0; // They have no more tickets to buy
11        } else {
12            totalTime += ticketsForTarget; // They can only buy as many as the target needs minus one
13            tickets[i] -= ticketsForTarget; // Subtract the bought tickets from their total needed tickets
14        }
15    }
16
17    // Round 2: Continue the purchasing process for remaining tickets
18    // this time including the target person buying their last ticket
19    for (let i = 0; i <= k; i++) {
20        if (tickets[i] > 0) {
21            totalTime += 1; // Add one extra time unit for every person including and before the target
22        }
23    }
24
25    return totalTime;
26}
27
Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

Time and Space Complexity

Time Complexity

The time complexity of the function is O(n), where n is the length of the tickets array. This is because the function contains a single loop over the tickets array, and the operations within the loop are constant-time computations, involving simple arithmetic and comparison.

Space Complexity

The space complexity of the function is O(1) because it uses a fixed amount of extra space – the ans variable for storing the cumulative time. No additional data structures are used that grow with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

Queue Intro

Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫