# Time Needed to Buy Tickets
**Difficulty:** EASY
[External](https://leetcode.com/problems/time-needed-to-buy-tickets)
Canonical: https://scaleengineer.com/dsa/problems/time-needed-to-buy-tickets
**Data structures:** Array, Queue
**Companies:** [X](https://scaleengineer.com/companies/x), [Komprise](https://scaleengineer.com/companies/komprise)
---
## Problem
There are `n` people in a line queuing to buy tickets, where the `0th` 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 `ith` 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 **initially** at position **k**(0-indexed) to finish buying tickets.

**Example 1:**

**Input:** tickets = \[2,3,2\], k = 2

**Output:** 6

**Explanation:**

* The queue starts as \[2,3,2\], where the kth person is underlined.
* After the person at the front has bought a ticket, the queue becomes \[3,2,1\] at 1 second.
* Continuing this process, the queue becomes \[2,1,2\] at 2 seconds.
* Continuing this process, the queue becomes \[1,2,1\] at 3 seconds.
* Continuing this process, the queue becomes \[2,1\] at 4 seconds. Note: the person at the front left the queue.
* Continuing this process, the queue becomes \[1,1\] at 5 seconds.
* Continuing this process, the queue becomes \[1\] at 6 seconds. The kth person has bought all their tickets, so return 6.

**Example 2:**

**Input:** tickets = \[5,1,1,1\], k = 0

**Output:** 8

**Explanation:**

* The queue starts as \[5,1,1,1\], where the kth person is underlined.
* After the person at the front has bought a ticket, the queue becomes \[1,1,1,4\] at 1 second.
* Continuing this process for 3 seconds, the queue becomes \[4\] at 4 seconds.
* Continuing this process for 4 seconds, the queue becomes \[\] at 8 seconds. The kth person has bought all their tickets, so return 8.

**Constraints:**

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

# Approaches
## Brute-Force Simulation using a Queue
This approach directly simulates the ticket-buying process as described in the problem. We use a queue to represent the line of people. Each person buys a ticket, and if they need more, they are sent to the back of the queue. We keep track of the elapsed time until the person at index `k` has bought all their tickets.
**Time:** O(N * max(tickets)). In the worst case, the person at `k` needs `tickets[k]` passes through the line. In each pass, there are at most `N` people. Thus, the total time is proportional to the product of the number of people and the number of tickets. · **Space:** O(N), where N is the number of people. This is for the queue which stores the indices of the people in line.
**Pros:** Straightforward to understand as it directly models the real-world process.; Correctly handles the state of the queue at every second.
**Cons:** Less efficient compared to other approaches, with a time complexity dependent on the number of tickets.; Uses extra space for the queue, which can be up to O(n).
### Explanation
The most intuitive way to solve this problem is to replicate the process exactly. We can use a queue, a data structure that perfectly models a first-in, first-out line.

1.  **Initialization**: We start by creating a queue and adding the initial indices of all people (`0, 1, ..., n-1`) into it. We also initialize a `time` counter to zero.
2.  **Simulation Loop**: The simulation runs in a loop. In each iteration, we simulate one second of time:
    - We take the person at the front of the queue (by dequeuing their index).
    - We increment our `time` counter.
    - This person buys one ticket, so we decrement their required ticket count in the `tickets` array.
    - We then check if this person was our target person at index `k` and if they have now bought all their tickets. If so, the simulation is over, and we return the current `time`.
    - If the person still has tickets to buy, they go to the back of the line, which we simulate by enqueuing their index.
    - If a person finishes buying all their tickets (and they are not the person at index `k` whose completion would stop the process), they simply leave the line and are not added back to the queue.

This process continues until the person at index `k` buys their last ticket.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < tickets.length; i++) {
            queue.add(i);
        }

        int time = 0;
        // The loop continues as long as the queue is not empty.
        // The condition to stop is checked inside the loop.
        while (!queue.isEmpty()) {
            int personIndex = queue.poll();
            time++;
            tickets[personIndex]--;

            if (personIndex == k && tickets[k] == 0) {
                return time;
            }

            if (tickets[personIndex] > 0) {
                queue.add(personIndex);
            }
        }
        return time; // Should not be reached given problem constraints
    }
}
```
### Algorithm
- Create a `Queue` and populate it with the indices of people, from `0` to `n-1`.
- Initialize a `time` variable to `0`.
- Start a loop that continues as long as the person at index `k` has tickets to buy.
- Inside the loop, dequeue the person's index `p` from the front of the queue.
- Increment the `time` counter.
- Decrement the ticket count for person `p`.
- If person `p` is the target person (`p == k`) and they have just finished buying tickets (`tickets[p] == 0`), return the total `time`.
- If person `p` still needs more tickets (`tickets[p] > 0`), add their index `p` back to the end of the queue.

## Simulation using an Array
This approach also simulates the process but avoids using an explicit queue data structure. Instead, we can use the `tickets` array itself and a pointer that iterates through it circularly to represent the line. This can be slightly more efficient in practice due to better memory locality and no overhead from queue operations.
**Time:** O(N * tickets[k]). The logic is equivalent to the queue simulation. The outer loop effectively runs `tickets[k]` times, and the inner loop runs `N` times for each pass. · **Space:** O(1), assuming we can modify the input `tickets` array. If not, O(N) would be required to hold a copy.
**Pros:** More space-efficient, using O(1) extra space if the input array can be modified.; May have slightly better performance than the queue approach due to avoiding queue overhead and having better cache-friendliness.
**Cons:** The time complexity is still not optimal and is similar to the queue-based approach.; The nested loop structure might seem inefficient, as it iterates over people who may have already finished buying tickets.
### Explanation
Instead of managing a separate queue of indices, we can simulate the round-robin nature of the line by repeatedly iterating over the `tickets` array. Each full iteration from index `0` to `n-1` represents one pass where everyone in the line gets a chance to buy a ticket.

1.  **Initialization**: We only need a `time` variable, initialized to `0`.
2.  **Simulation**: We use nested loops. The outer loop represents the passage of time and continues until our target person at index `k` is done. The inner loop iterates from `i = 0` to `n-1`, representing one round of ticket buying.
    - For each person `i`, if they have tickets left (`tickets[i] > 0`), we simulate them buying one ticket by decrementing `tickets[i]` and incrementing `time`.
    - A crucial check is performed after every single second (every time `time` is incremented): we see if the person at index `k` has just finished. If `tickets[k]` becomes `0`, we have found our answer and can immediately return the current `time`.

This method modifies the input array `tickets` to keep track of the remaining tickets for each person.

```java
class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        int time = 0;
        int n = tickets.length;
        
        // This outer loop can be a while(true) or while(tickets[k] > 0).
        // It ensures we keep making passes until person k is done.
        while (tickets[k] > 0) {
            for (int i = 0; i < n; i++) {
                // Process person i only if they still need tickets.
                if (tickets[i] > 0) {
                    tickets[i]--;
                    time++;
                }
                // Check for completion condition after each second.
                if (i == k && tickets[k] == 0) {
                    return time;
                }
            }
        }
        
        return time;
    }
}
```
### Algorithm
- Initialize `time = 0`.
- Use a `while` loop that continues as long as the person at `k` needs tickets (`tickets[k] > 0`).
- Inside the `while` loop, start a `for` loop to iterate through all people from index `i = 0` to `n-1`.
- For each person `i`, check if they still need tickets (`tickets[i] > 0`).
- If they do, decrement their ticket count (`tickets[i]--`) and increment the total `time`.
- After each ticket purchase, check if the person who just bought a ticket was the target person (`i == k`) and if they are now finished (`tickets[k] == 0`). If so, break the loops and return the `time`.

## One-Pass Mathematical Approach
The most efficient approach involves a single pass over the `tickets` array. Instead of simulating the process second-by-second, we can logically deduce the total time by calculating how many tickets each person will have bought by the time the person at index `k` finishes.
**Time:** O(N), where N is the number of people. We only need to iterate through the `tickets` array once. · **Space:** O(1), as we only use a few variables to store the running total and target value.
**Pros:** Extremely efficient, with optimal O(N) time complexity.; Uses constant O(1) extra space.; Avoids the overhead of simulation and data structures.
**Cons:** The logic is less direct and requires a careful analytical step to derive the formula, making it potentially harder to come up with during an interview.
### Explanation
We can solve this problem by thinking about the state of the system when the person at index `k` finishes. Let `T_k = tickets[k]` be the number of tickets person `k` needs.

Person `k` will go through the line `T_k` times. This means there will be `T_k - 1` full rounds where everyone gets a chance to buy a ticket, followed by a final, partial round.

Let's analyze the total time by summing up the time spent by each person:

1.  **For people at indices `i <= k` (including person `k`):**
    - These people are either ahead of or are person `k`. They will be in the line for all `T_k` rounds that person `k` is. 
    - If a person `i` needs `tickets[i]` tickets, and `tickets[i] < T_k`, they will finish early after buying all `tickets[i]` tickets.
    - If `tickets[i] >= T_k`, they will buy one ticket in each of the `T_k` rounds alongside person `k`.
    - Therefore, each person `i <= k` contributes `min(tickets[i], T_k)` seconds to the total time.

2.  **For people at indices `i > k`:**
    - These people are behind person `k` in the line.
    - They will participate fully in the first `T_k - 1` rounds.
    - In the final round (the `T_k`-th round for person `k`), person `k` buys their last ticket and leaves. The process stops then. The people at `i > k` do not get a chance to buy a ticket in this final round.
    - Therefore, each person `i > k` contributes `min(tickets[i], T_k - 1)` seconds to the total time.

By summing these contributions in a single loop, we can find the answer in linear time.

```java
class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        int time = 0;
        int targetTickets = tickets[k];

        for (int i = 0; i < tickets.length; i++) {
            if (i <= k) {
                time += Math.min(tickets[i], targetTickets);
            } else { // i > k
                time += Math.min(tickets[i], targetTickets - 1);
            }
        }
        return time;
    }
}
```
### Algorithm
- Initialize `time = 0`.
- Store the number of tickets the person at `k` wants to buy in a variable, let's call it `target_tickets`.
- Iterate through the `tickets` array with an index `i` from `0` to `n-1`.
- For each person `i`, calculate their contribution to the total time:
  - If the person is at or before `k` in the line (`i <= k`), they will get to buy tickets in every round that `k` participates in. The number of tickets they buy is the minimum of their own requirement and `k`'s requirement. So, add `min(tickets[i], target_tickets)` to `time`.
  - If the person is after `k` in the line (`i > k`), they will participate in one fewer round than `k`. This is because the process stops as soon as `k` buys their last ticket, and people after `k` in that final round don't get a turn. So, add `min(tickets[i], target_tickets - 1)` to `time`.
- After the loop finishes, `time` will hold the total time required.

# Solutions
### Java

```java
class Solution { public int timeRequiredToBuy ( int [] tickets , int k ) { int ans = 0 ; for ( int i = 0 ; i < tickets . length ; i ++) { if ( i <= k ) { ans += Math . min ( tickets [ k ], tickets [ i ]); } else { ans += Math . min ( tickets [ k ] - 1 , tickets [ i ]); } } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  int timeRequiredToBuy(vector<int> &tickets, int k) {
    int ans = 0;
    for (int i = 0; i < tickets.size(); ++i) {
      if (i <= k) {
        ans += min(tickets[k], tickets[i]);
      } else {
        ans += min(tickets[k] - 1, tickets[i]);
      }
    }
    return ans;
  }
};

```

### Python

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