LC2073. Time Needed to Buy Tickets

Approach 2: Math (Optimal)

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        total = 0
 
        for i in range(len(tickets)):
            if i <= k:
                total += min(tickets[i], tickets[k])
            else:
                # Once we get to kth person, they get one ticket
                # so remaining tickets is tickets[k] - 1 and we
                # just need to compare this new number against folks
                # behind him.
                total += min(tickets[i], tickets[k] - 1)
 
        return total    

Terse version (H/T: @sudomakes)

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        return sum(min(tickets[i], tickets[k] - int(i > k)) for i in range(len(tickets)))

Complexity

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

Approach 1: Using Double-Ended Queue

from collections import deque
 
class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        d = deque(tickets)
        total = 0
        n = len(tickets)
        k += 1
 
        while n > 0:
            remaining = d.popleft()
            total += 1
 
            # kth person is in front
            if k == 1:
                if remaining == 1:
                    return total
                
                k = n
                d.append(remaining - 1)
            else:
                if remaining == 1:
                    n -= 1
                else:
                    d.append(remaining - 1)
                
                k -= 1
        
        return total

Complexity

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