{x}
blog image

Time Needed to Buy Tickets

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

Solution Explanation: Time Needed to Buy Tickets

This problem simulates a queue of people buying tickets. The goal is to determine the time it takes for the person at index k to finish buying their tickets.

Core Idea: The solution leverages the observation that the time taken for the k-th person depends on the number of tickets they need and the number of tickets bought by those in front of and behind them.

Algorithm:

  1. Iterate Through the Queue: The algorithm iterates through the tickets array, representing each person in the queue.

  2. Calculate Time for Each Person: For each person i:

    • If i <= k (person is in front of or at index k): The maximum number of tickets this person can buy before the k-th person is finished is min(tickets[i], tickets[k]).
    • If i > k (person is behind the k-th person): The maximum number of tickets this person can buy before the k-th person is finished is min(tickets[i], tickets[k] - 1). (The k-th person needs one fewer ticket than the person in front of them).

  3. Accumulate Time: The total time is the sum of the time each person takes to buy their tickets.

Time Complexity Analysis:

The algorithm iterates through the tickets array once. Therefore, the time complexity is O(n), where n is the length of the tickets array.

Space Complexity Analysis:

The algorithm uses a constant amount of extra space, regardless of the input size. Therefore, the space complexity is O(1).

Code Examples (Python, Java, C++, Go, and TypeScript):

The provided code examples implement this algorithm in several popular programming languages. Each example follows the same logic:

  • It initializes a variable ans to 0 to store the total time.
  • It iterates through the tickets array using a for loop.
  • Inside the loop, it calculates the time each person takes (min(tickets[i], tickets[k] if i <= k else tickets[k] - 1)) and adds it to ans.
  • Finally, it returns the total time ans.

The code variations only differ in syntax and specific function calls (e.g., min() vs. Math.min()). The core logic remains consistent across all languages.

This efficient, single-pass approach provides an optimal solution to the "Time Needed to Buy Tickets" problem.