Problem 10.1 · Queue, Deque and Monotonic QueueEasy

Time Needed to Buy Tickets

What it teaches: Simulate with a queue first, then notice the formula that skips the simulation.

Practise it on judges as “Time Needed to Buy Tickets”.

The problem

People stand in a line; person i wants tickets[i] tickets. Each second, the person at the front buys one ticket; if they still need more, they go to the back of the line. Return the time for person k to finish buying.

Example 1

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

Example 2

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

Constraints

1 ≤ n ≤ 100
1 ≤ tickets[i] ≤ 100

Pattern clues in the wording

→ A described turn-taking process
→ Small limits allow simulation; a formula is faster

These clues point to Running State in One Pass: Walk the input once and keep a few variables (best so far, minimum so far, a count) that summarise everything seen.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	tickets = [2,3,2] k = 2	6
2	tickets = [5,1,1,1] k = 0	8

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Simulate with a queue · O(n · max tickets)2. Optimal: count directly · O(n)

Simulate with a queue

Time O(n · max tickets) Space O(n)

Queue of indexes. Each second, poll the front, decrement their tickets, re-offer if they need more. Stop when person k reaches 0.

Approach 1

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        int[] left = tickets.clone();
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < left.length; i++) q.offer(i);
        int time = 0;
        while (true) {
            int i = q.poll();
            left[i]--;
            time++;
            if (i == k && left[i] == 0) return time;
            if (left[i] > 0) q.offer(i);
        }
    }
}

Verdict: Fine for the limits, and a good first answer.

Optimal: count directly

Time O(n) Space O(1)

Someone at or before k buys min(tickets[i], tickets[k]) tickets before k finishes. Someone after k buys min(tickets[i], tickets[k] − 1), because k finishes in the round before their last turn. Add them up.

Approach 2

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

Verdict: No simulation needed.

Before you submit

Edge cases and common mistakes

Test these inputs

k is first in line
k is last
k needs only one ticket

Mistakes people make

Counting people behind k with the full tickets[k] (they get one turn fewer).

Interview

Follow-up questions

When is simulation the right answer in an interview?