2073. Time Needed to Buy Tickets - Explanation

Description

There are n people in a line queuing to buy tickets, where the 0-th 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 i-th 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

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Queue data structure - Simulating the ticket line with FIFO behavior
Array iteration - Processing elements in circular order using modulo arithmetic
Mathematical reasoning - The optimal solution calculates contributions directly without simulation

1. Queue

Intuition

We can simulate the ticket buying process exactly as described. People stand in a queue, and each person buys one ticket at a time before going to the back of the line. We continue this process until the person at position k has bought all their tickets.

Using a queue data structure naturally models this behavior. We track each person's index and decrement their remaining tickets each time they reach the front. When someone finishes buying all their tickets, they leave the queue. The simulation ends when the person at index k completes their purchase.

Algorithm

Initialize a queue with indices 0 to n-1 representing each person's position.
Track the total time elapsed starting at 0.
While the queue is not empty, dequeue the front person and increment time by 1.
Decrement that person's ticket count in the array.
If their count reaches 0 and their index equals k, return the current time.
If their count is still positive, add them back to the queue.

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        n = len(tickets)
        q = deque()

        for i in range(n):
            q.append(i)

        time = 0
        while q:
            time += 1
            cur = q.popleft()
            tickets[cur] -= 1
            if tickets[cur] == 0:
                if cur == k:
                    return time
            else:
                q.append(cur)
        return time

public class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        int n = tickets.length;
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            queue.add(i);
        }

        int time = 0;
        while (!queue.isEmpty()) {
            time++;
            int cur = queue.poll();
            tickets[cur]--;
            if (tickets[cur] == 0) {
                if (cur == k) {
                    return time;
                }
            } else {
                queue.add(cur);
            }
        }
        return time;
    }
}

class Solution {
public:
    int timeRequiredToBuy(vector<int>& tickets, int k) {
        int n = tickets.size();
        queue<int> q;

        for (int i = 0; i < n; i++) {
            q.push(i);
        }

        int time = 0;
        while (!q.empty()) {
            time++;
            int cur = q.front();
            q.pop();
            tickets[cur]--;
            if (tickets[cur] == 0) {
                if (cur == k) {
                    return time;
                }
            } else {
                q.push(cur);
            }
        }
        return time;
    }
};

class Solution {
    /**
     * @param {number[]} tickets
     * @param {number} k
     * @return {number}
     */
    timeRequiredToBuy(tickets, k) {
        let n = tickets.length;
        let queue = new Queue();

        for (let i = 0; i < n; i++) {
            queue.push(i);
        }

        let time = 0;
        while (queue.size() > 0) {
            time++;
            let cur = queue.pop();
            tickets[cur]--;
            if (tickets[cur] === 0) {
                if (cur === k) {
                    return time;
                }
            } else {
                queue.push(cur);
            }
        }
        return time;
    }
}

func timeRequiredToBuy(tickets []int, k int) int {
    n := len(tickets)
    queue := make([]int, 0, n)

    for i := 0; i < n; i++ {
        queue = append(queue, i)
    }

    time := 0
    for len(queue) > 0 {
        time++
        cur := queue[0]
        queue = queue[1:]
        tickets[cur]--
        if tickets[cur] == 0 {
            if cur == k {
                return time
            }
        } else {
            queue = append(queue, cur)
        }
    }
    return time
}

class Solution {
    fun timeRequiredToBuy(tickets: IntArray, k: Int): Int {
        val n = tickets.size
        val queue: Queue<Int> = LinkedList()

        for (i in 0 until n) {
            queue.add(i)
        }

        var time = 0
        while (queue.isNotEmpty()) {
            time++
            val cur = queue.poll()
            tickets[cur]--
            if (tickets[cur] == 0) {
                if (cur == k) {
                    return time
                }
            } else {
                queue.add(cur)
            }
        }
        return time
    }
}

class Solution {
    func timeRequiredToBuy(_ tickets: [Int], _ k: Int) -> Int {
        var tickets = tickets
        let n = tickets.count
        var queue = [Int]()

        for i in 0..<n {
            queue.append(i)
        }

        var time = 0
        while !queue.isEmpty {
            time += 1
            let cur = queue.removeFirst()
            tickets[cur] -= 1
            if tickets[cur] == 0 {
                if cur == k {
                    return time
                }
            } else {
                queue.append(cur)
            }
        }
        return time
    }
}

impl Solution {
    pub fn time_required_to_buy(mut tickets: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        let n = tickets.len();
        let mut queue: VecDeque<usize> = (0..n).collect();

        let mut time = 0;
        while let Some(cur) = queue.pop_front() {
            time += 1;
            tickets[cur] -= 1;
            if tickets[cur] == 0 {
                if cur == k {
                    return time;
                }
            } else {
                queue.push_back(cur);
            }
        }
        time
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $n$ is the size of the input array and $m$ is the maximum value in the input array.

2. Iteration

Intuition

Instead of using a queue, we can simulate the process by iterating through the array in a circular manner. We keep a pointer that cycles through positions 0, 1, 2, ..., n-1, 0, 1, ... and skip anyone who has already finished buying tickets.

This approach eliminates the need for a separate queue data structure while achieving the same simulation. We track time and decrement ticket counts as we cycle through, stopping when the person at position k finishes.

Algorithm

Initialize an index pointer at 0 and time counter at 0.
Loop indefinitely, incrementing time and decrementing the current person's ticket count.
If the current person finishes (count becomes 0) and their index equals k, return time.
Move the index to the next position using modulo: idx = (idx + 1) % n.
Skip over any person with zero tickets by advancing the index.

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        n = len(tickets)
        idx = 0

        time = 0
        while True:
            time += 1
            tickets[idx] -= 1
            if tickets[idx] == 0:
                if idx == k:
                    return time
            idx = (idx + 1) % n
            while tickets[idx] == 0:
                idx = (idx + 1) % n

        return time

public class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        int n = tickets.length;
        int idx = 0;

        int time = 0;
        while (true) {
            time++;
            tickets[idx]--;
            if (tickets[idx] == 0) {
                if (idx == k) {
                    return time;
                }
            }
            idx = (idx + 1) % n;
            while (tickets[idx] == 0) {
                idx = (idx + 1) % n;
            }
        }
    }
}

class Solution {
public:
    int timeRequiredToBuy(vector<int>& tickets, int k) {
        int n = tickets.size();
        int idx = 0;

        int time = 0;
        while (true) {
            time++;
            tickets[idx]--;
            if (tickets[idx] == 0) {
                if (idx == k) {
                    return time;
                }
            }
            idx = (idx + 1) % n;
            while (tickets[idx] == 0) {
                idx = (idx + 1) % n;
            }
        }

        return time;
    }
};

class Solution {
    /**
     * @param {number[]} tickets
     * @param {number} k
     * @return {number}
     */
    timeRequiredToBuy(tickets, k) {
        let n = tickets.length;
        let idx = 0;

        let time = 0;
        while (true) {
            time++;
            tickets[idx]--;
            if (tickets[idx] === 0) {
                if (idx === k) {
                    return time;
                }
            }
            idx = (idx + 1) % n;
            while (tickets[idx] === 0) {
                idx = (idx + 1) % n;
            }
        }

        return time;
    }
}

func timeRequiredToBuy(tickets []int, k int) int {
    n := len(tickets)
    idx := 0

    time := 0
    for {
        time++
        tickets[idx]--
        if tickets[idx] == 0 {
            if idx == k {
                return time
            }
        }
        idx = (idx + 1) % n
        for tickets[idx] == 0 {
            idx = (idx + 1) % n
        }
    }
}

class Solution {
    fun timeRequiredToBuy(tickets: IntArray, k: Int): Int {
        val n = tickets.size
        var idx = 0

        var time = 0
        while (true) {
            time++
            tickets[idx]--
            if (tickets[idx] == 0) {
                if (idx == k) {
                    return time
                }
            }
            idx = (idx + 1) % n
            while (tickets[idx] == 0) {
                idx = (idx + 1) % n
            }
        }
    }
}

class Solution {
    func timeRequiredToBuy(_ tickets: [Int], _ k: Int) -> Int {
        var tickets = tickets
        let n = tickets.count
        var idx = 0

        var time = 0
        while true {
            time += 1
            tickets[idx] -= 1
            if tickets[idx] == 0 {
                if idx == k {
                    return time
                }
            }
            idx = (idx + 1) % n
            while tickets[idx] == 0 {
                idx = (idx + 1) % n
            }
        }
    }
}

impl Solution {
    pub fn time_required_to_buy(mut tickets: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        let n = tickets.len();
        let mut idx = 0;
        let mut time = 0;

        loop {
            time += 1;
            tickets[idx] -= 1;
            if tickets[idx] == 0 && idx == k {
                return time;
            }
            idx = (idx + 1) % n;
            while tickets[idx] == 0 {
                idx = (idx + 1) % n;
            }
        }
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(1)$

Where $n$ is the size of the input array and $m$ is the maximum value in the input array.

3. Iteration (One Pass)

Intuition

Instead of simulating the entire process, we can calculate the answer directly. Consider how many times each person will buy a ticket before person k finishes.

For people standing at or before position k, they will buy tickets at most tickets[k] times, since they get to buy before person k in each round. For people standing after position k, they will buy at most tickets[k] - 1 times, since in the final round, person k finishes before they get another turn. Each person's contribution is capped by their own ticket needs.

Algorithm

Initialize res to 0.
Iterate through each person from index 0 to n-1.
For person at index i <= k, add min(tickets[i], tickets[k]) to the result.
For person at index i > k, add min(tickets[i], tickets[k] - 1) to the result.
Return the total sum.

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        res = 0

        for i in range(len(tickets)):
            if i <= k:
                res += min(tickets[i], tickets[k])
            else:
                res += min(tickets[i], tickets[k] - 1)

        return res

public class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        int res = 0;

        for (int i = 0; i < tickets.length; i++) {
            if (i <= k) {
                res += Math.min(tickets[i], tickets[k]);
            } else {
                res += Math.min(tickets[i], tickets[k] - 1);
            }
        }

        return res;
    }
}

class Solution {
public:
    int timeRequiredToBuy(vector<int>& tickets, int k) {
        int res = 0;

        for (int i = 0; i < tickets.size(); i++) {
            if (i <= k) {
                res += min(tickets[i], tickets[k]);
            } else {
                res += min(tickets[i], tickets[k] - 1);
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} tickets
     * @param {number} k
     * @return {number}
     */
    timeRequiredToBuy(tickets, k) {
        let res = 0;

        for (let i = 0; i < tickets.length; i++) {
            if (i <= k) {
                res += Math.min(tickets[i], tickets[k]);
            } else {
                res += Math.min(tickets[i], tickets[k] - 1);
            }
        }

        return res;
    }
}

func timeRequiredToBuy(tickets []int, k int) int {
    res := 0

    for i := 0; i < len(tickets); i++ {
        if i <= k {
            res += min(tickets[i], tickets[k])
        } else {
            res += min(tickets[i], tickets[k]-1)
        }
    }

    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    fun timeRequiredToBuy(tickets: IntArray, k: Int): Int {
        var res = 0

        for (i in tickets.indices) {
            res += if (i <= k) {
                minOf(tickets[i], tickets[k])
            } else {
                minOf(tickets[i], tickets[k] - 1)
            }
        }

        return res
    }
}

class Solution {
    func timeRequiredToBuy(_ tickets: [Int], _ k: Int) -> Int {
        var res = 0

        for i in 0..<tickets.count {
            if i <= k {
                res += min(tickets[i], tickets[k])
            } else {
                res += min(tickets[i], tickets[k] - 1)
            }
        }

        return res
    }
}

impl Solution {
    pub fn time_required_to_buy(tickets: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        let mut res = 0;
        for i in 0..tickets.len() {
            if i <= k {
                res += tickets[i].min(tickets[k]);
            } else {
                res += tickets[i].min(tickets[k] - 1);
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Using the Wrong Bound for People After Position k

For people standing after position k, they only get tickets[k] - 1 turns before person k finishes (since person k completes on their final turn before these people get another chance). A common mistake is using tickets[k] for everyone, which overcounts the time contribution from people behind position k.

Confusing Position Index With Ticket Count

When calculating contributions, you must use min(tickets[i], tickets[k]) for i <= k and min(tickets[i], tickets[k] - 1) for i > k. Some solutions incorrectly compare indices instead of ticket counts, or forget to take the minimum, leading to counting more tickets than a person actually needs to buy.