LeetCode 2073 - Time Needed to Buy Tickets

This problem describes a queue of n people, each wanting to buy a certain number of tickets. The input is an array tickets where tickets[i] represents how many tickets the i-th person wants.

leetcodeeasyarrayqueuesimulation

LeetCode Problem 2073

Difficulty: 🟢 Easy
Topics: Array, Queue, Simulation

Solution

Problem Understanding

This problem describes a queue of n people, each wanting to buy a certain number of tickets. The input is an array tickets where tickets[i] represents how many tickets the i-th person wants. The process works like a real-life queue: each person buys one ticket at a time, taking exactly 1 second per ticket, and if they still need more tickets, they move to the end of the line. Once a person has bought all their tickets, they leave the queue.

The question specifically asks for the total time it takes for the person at position k (0-indexed) to finish buying all their tickets. The position of k is fixed in the initial array, but as people move to the end of the line, the position of k will shift relative to the front of the queue.

The constraints indicate that n and tickets[i] are small (<= 100), so a direct simulation approach is feasible. Important edge cases include when the person at k is at the front, when they are at the back, when they need only one ticket, and when they need as many as 100 tickets.

Approaches

The brute-force approach is to simulate the queue exactly as described. We iterate through the queue in order, decrementing each person's ticket count by 1 and moving them to the back if they still have tickets left. We continue until the person at index k has bought all their tickets. This works correctly but involves repeatedly moving people in a queue, which could be inefficient in terms of repeated list operations. With n up to 100 and ticket counts up to 100, this is acceptable but not elegant.

The optimal approach leverages a key observation: the time taken for person k is determined by how many full rounds they participate in. Specifically, each person i in the queue will contribute min(tickets[i], tickets[k]) seconds to the total time. If i is positioned after k, they contribute min(tickets[i], tickets[k]-1) seconds because person k finishes after their last ticket, so people after k in that final round will not add extra time. This avoids simulating the queue entirely and gives a simple O(n) solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * max(tickets[i])) O(n) Simulates the queue step by step
Optimal O(n) O(1) Uses direct counting per person based on rounds

Algorithm Walkthrough

  1. Initialize time = 0. This variable will track the cumulative seconds required for person k.
  2. Iterate over each person i in the queue from 0 to n-1.
  3. If person i is before or at k, add min(tickets[i], tickets[k]) to time. This counts all full rounds and the last partial round for k.
  4. If person i is after k, add min(tickets[i], tickets[k]-1) to time. They only participate in rounds before k finishes their last ticket.
  5. Return time as the total time required.

Why it works: Each person's contribution to the total time is at most tickets[k], except for people after k who only participate in rounds before k buys their last ticket. Summing these contributions gives the exact number of seconds required without simulating the queue.

Python Solution

from typing import List

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        total_time = 0
        for i, t in enumerate(tickets):
            if i <= k:
                total_time += min(t, tickets[k])
            else:
                total_time += min(t, tickets[k] - 1)
        return total_time

In this Python implementation, we loop through the tickets array. If a person is at or before k, they will buy tickets in all rounds up to and including the last one for k. People after k only participate in rounds before k's last ticket. Using min() ensures we do not overcount contributions. The final total_time is returned.

Go Solution

func timeRequiredToBuy(tickets []int, k int) int {
    totalTime := 0
    for i, t := range tickets {
        if i <= k {
            if t < tickets[k] {
                totalTime += t
            } else {
                totalTime += tickets[k]
            }
        } else {
            if t < tickets[k]-1 {
                totalTime += t
            } else {
                totalTime += tickets[k] - 1
            }
        }
    }
    return totalTime
}

In Go, we follow the same logic as Python. We avoid unnecessary slices or queues and directly accumulate the total seconds. Go does not have a min function for integers in the standard library, so we use explicit conditionals.

Worked Examples

Example 1: tickets = [2,3,2], k = 2

Step Queue State Action Time
0 [2,3,2] Person 0 buys 1 1
1 [1,3,2] Person 1 buys 1 2
2 [1,2,2] Person 2 buys 1 3
3 [1,2,1] Person 0 buys 1 4
4 [0,2,1] Person 1 buys 1 5
5 [0,1,1] Person 2 buys 1 6

Person k=2 finishes at time 6.

Example 2: tickets = [5,1,1,1], k = 0

Using the optimal approach:

Person 0 wants 5 tickets. People after index 0 contribute at most min(tickets[i], tickets[0]-1) = min(tickets[i], 4):

  • i=0 → min(5,5) = 5
  • i=1 → min(1,4) = 1
  • i=2 → min(1,4) = 1
  • i=3 → min(1,4) = 1

Total time = 5 + 1 + 1 + 1 = 8

Matches the simulation.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass over the tickets array; no nested loops or queue simulation
Space O(1) Only uses a single accumulator variable, no additional data structures

The complexity is efficient and scales linearly with the number of people. Simulation approaches with nested operations are still acceptable for n ≤ 100, but the optimal approach avoids repeated list operations.

Test Cases

# Provided examples
assert Solution().timeRequiredToBuy([2,3,2], 2) == 6  # kth person at back
assert Solution().timeRequiredToBuy([5,1,1,1], 0) == 8  # kth person at front

# Edge cases
assert Solution().timeRequiredToBuy([1], 0) == 1  # Single person, single ticket
assert Solution().timeRequiredToBuy([100], 0) == 100  # Single person, max tickets
assert Solution().timeRequiredToBuy([1,1,1,1], 3) == 4  # kth at end, each 1 ticket
assert Solution().timeRequiredToBuy([1,2,3,4], 2) == 7  # kth in middle
assert Solution().timeRequiredToBuy([2,2,2,2], 0) == 8  # uniform tickets, kth at front
Test Why
[2,3,2], k=2 Checks correct counting when kth is at the back
[5,1,1,1], k=0 Checks correct counting when kth is at front
[1], k=0 Minimum input size
[100], k=0 Maximum ticket count for single person
[1,1,1,1], k=3 Checks kth at end with minimal tickets
[1,2,3,4], k=2 kth in middle of variable tickets
[2,2,2,2], k=0 Uniform tickets

Edge Cases

One edge case is when there is only one person in the queue. The algorithm correctly returns the number of tickets they want, because min(tickets[i], tickets[k]) evaluates to the ticket count itself.

A second edge case is when the kth person is at the end of the queue. People after k do not exist, so the code must handle the else branch correctly without errors. The formula automatically handles this by ignoring non-existent contributions.

A third edge case is when some people want many more tickets than k, but are positioned after k. The algorithm correctly counts only tickets[k]-1 for these people because the kth person finishes their last ticket before those after can fully buy their tickets. This