Time Needed to Buy Tickets

How it works

Instead of simulating the entire process, we can calculate the answer directly. Consider how many times each person will buy a ticket before person k finishes.

For people standing at or before position k, they will buy tickets at most tickets[k] times, since they get to buy before person k in each round. For people standing after position k, they will buy at most tickets[k] - 1 times, since in the final round, person k finishes before they get another turn. Each person's contribution is capped by their own ticket needs.

Steps

1. Initialize res to 0.
2. Iterate through each person from index 0 to n-1.
3. For person at index i <= k, add min(tickets[i], tickets[k]) to the result.
4. For person at index i > k, add min(tickets[i], tickets[k] - 1) to the result.
5. Return the total sum.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Using the Wrong Bound for People After Position k

For people standing after position k, they only get tickets[k] - 1 turns before person k finishes (since person k completes on their final turn before these people get another chance). A common mistake is using tickets[k] for everyone, which overcounts the time contribution from people behind position k.

Confusing Position Index With Ticket Count

When calculating contributions, you must use min(tickets[i], tickets[k]) for i <= k and min(tickets[i], tickets[k] - 1) for i > k. Some solutions incorrectly compare indices instead of ticket counts, or forget to take the minimum, leading to counting more tickets than a person actually needs to buy.

from typing import List

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        res = 0

        for i in range(len(tickets)):
            if i <= k:
                res += min(tickets[i], tickets[k])
            else:
                res += min(tickets[i], tickets[k] - 1)

        return res

class Solution {
public:
    int timeRequiredToBuy(vector<int>& tickets, int k) {
        int res = 0;

        for (int i = 0; i < tickets.size(); i++) {
            if (i <= k) {
                res += min(tickets[i], tickets[k]);
            } else {
                res += min(tickets[i], tickets[k] - 1);
            }
        }

        return res;
    }
};