💬 Discord
Sign In
NeetCode #86LC-2073EasyArrays & Hashing
← Back to All Problems

#86 · #2073 · Time Needed to Buy Tickets(买票需要的时间)

📌 Problem Statement & Constraints

There are n people in a queue, tickets[i] is the number of tickets person i wants, and each ticket takes exactly 1 second to buy. A person leaves the queue after buying all their tickets. Return the time taken for the person at position k (0-indexed) to finish. Constraints: 1 <= n <= 100, 1 <= tickets[i] <= 100.

💡 Core Algorithmic Approaches

  1. Only people at or before position k can buy more than tickets[k] tickets before k finishes.
  2. People before k (including k) buy at most min(tickets[i], tickets[k]) tickets in that window.
  3. People after k get at most tickets[k] - 1 turns, since k leaves before they would need the last round.
  4. Summing these bounds gives the answer directly in O(n), avoiding a full round-by-round simulation.

💻 Benchmark Python3 Implementation

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        target = tickets[k]
        total = 0
        for i, t in enumerate(tickets):
            if i <= k:
                total += min(t, target)      # gets at most tickets[k] turns
            else:
                total += min(t, target - 1)  # k leaves before the final round
        return total

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with O(1) work per person.
💾 Space Complexity
O(1): two counters.

⚠️ Interview Pitfalls & Follow-ups

  • Using tickets[k] for everyone after k: they get one fewer turn, because k finishes and leaves before their last round completes.
  • Simulating the queue round by round: O(sum(tickets)) which can be 10^4 here -- acceptable, but the direct formula is cleaner and generalises.
  • Off-by-one on the i <= k boundary: person k themselves must use the full tickets[k], so the condition is inclusive.
  • Multiplying tickets[k] * n: ignores that some people want fewer tickets.