2073. Time Needed to Buy Tickets - Explanation

1. 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

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

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

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)

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

Time & Space Complexity

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