Time needed to Buy and tickets

Problem Link

2073. Time Needed to Buy Tickets – LeetCode

Problem Statement

There are n people in a queue, and each person i has a certain number of tickets to buy, denoted by tickets[i].

The person at index 0 is at the front of the queue.

Each second, the person at the front of the queue:

Buys 1 ticket.
If they still have tickets left, they go to the end of the queue.
Otherwise, they leave the queue.

Return the total time (in seconds) it takes for the person at position k (0-indexed) to finish buying all their tickets.

Examples

Example 1:

Input: tickets = [2,3,2], k = 2
Output: 6

Explanation:
- Person 0 buys 1 ticket → [1,3,2]
- Person 1 buys 1 ticket → [1,2,2]
- Person 2 buys 1 ticket → [1,2,1]
- Person 0 buys 1 ticket → [0,2,1]
- Person 1 buys 1 ticket → [0,1,1]
- Person 2 buys 1 ticket → [0,1,0] ← Done

Example 2:

Input: tickets = [5,1,1,1], k = 0
Output: 8

Constraints

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

Intuition

We simulate the ticket buying process second by second:

Traverse the queue circularly.
If a person has tickets > 0, they buy one and go to the end.
Track the total seconds until person at index k finishes buying all their tickets.

This problem mimics a round-robin scheduling system and is straightforward to simulate with an index pointer.

Approach: Simulation with Circular Index

Initialize:
- t = 0 to count time
- i = 0 as the index pointer
While person at position k has tickets[k] > 0:
- If current person has tickets[i] > 0, decrement ticket count and increment time.
- Move to next person by incrementing i.
- If i == arr.length, reset i = 0 to cycle back.
When tickets[k] == 0, return t.

Java Code

class Solution {
    public int timeRequiredToBuy(int[] arr, int k) {
        int t = 0;
        int i = 0;

        while (arr[k] > 0) {
            if (i < arr.length && arr[i] > 0) {
                arr[i]--;
                t++;
                i++;
            } else if (i == arr.length) {
                i = 0;
            } else {
                i++;
            }
        }

        return t;
    }
}

Time and Space Complexity

Metric	Value
Time Complexity	`O(n * max(tickets))`
Space Complexity	`O(1)`
Explanation	We loop through the queue circularly until person `k` is done.

Dry Run

Input:

tickets = [2, 3, 2], k = 2

Process:

Time	Tickets	Notes
0	[2,3,2]	Start
1	[1,3,2]	0 buys 1
2	[1,2,2]	1 buys 1
3	[1,2,1]	2 buys 1
4	[0,2,1]	0 buys last
5	[0,1,1]	1 buys again
6	[0,1,0]	2 buys last → done

Output:

Alternate Approach (Math Based)

We can compute the time directly without simulation by summing up how many tickets each person contributes up to and including k:

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

This gives O(n) time complexity without modifying the array.

Conclusion

This problem is a classic example of round-robin simulation and helps strengthen understanding of:

Circular iteration
Index control
Queue simulation

The math-based approach is more efficient for interviews but the simulation is intuitive for understanding the flow.