2073. Time Needed to Buy Tickets - Explanation

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
    }
}

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
            }
        }
    }
}

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
    }
}

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.