2073. Time Needed to Buy Tickets¶

Description¶

There are n people in a line queuing to buy tickets, where the 0^th 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 number of tickets that the i^th person would like to buy is tickets[i].

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 tickets.

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 position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds.

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 position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds.

Constraints:

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

Solution 1: Simulation without Queue¶

In this solution, we're going to solve the problem by simulating the process of buying tickets.

We create a accumulator variable named seconds.
Loop through the tickets array and buy one ticket for each person if they haven't bought sufficient tickets.
If the person at position k has bought all the tickets, return the seconds value.

Time complexity: O(n^2)

The outer while loop runs takes O(n) in the worst case where n is the number of tickets.
The inner for loop runs n times in the worst case, which also depends on the number of tickets.
Therefore, the total time complexity is O(n * n) = O(n^2) due to nested loops.

Space complexity: O(1)

tickets we be excluded from the space complexity analysis as it's an input.
seconds variable will take constant space once it's declared regardless of the input size. Therefore, the total space complexity is O(1).
The total space complexity is O(1).

TypeScript

function timeRequiredToBuy(tickets: number[], k: number): number {

    // Accumulate the seconds
    let seconds = 0;

    // Keep buying tickets until `tickets[k]` is 0
    while(tickets.length > 0) {
        for(var i = 0; i < tickets.length; i++) {
            if (tickets[k] == 0) {
                return seconds;
            }
            if (tickets[i] > 0) {
                tickets[i]--;
                seconds++;
            }
        }

    }
    return seconds;
};

Solution 2: Simulation with Queue¶

It have same concept as the previous solution, but we're going to use a queue to keep track of the people who haven't bought all the tickets.

TypeScript