2073. Time Needed to Buy Tickets
Problem Description
In this problem, there are n
individuals standing in a line to purchase tickets, with the queue arranged such that the 0th
person is at the start of the line and the (n - 1)th
person is at the end of the line. An array tickets
of length n
is provided, where each element tickets[i]
denotes the number of tickets the ith
person wishes to buy.
The purchase process is such that each person requires exactly 1 second
to buy a single ticket, and can only buy one ticket at a time. After buying a ticket, if a person wants to buy more, they must go to the end of the line to purchase another ticket. This transition is assumed to be instantaneous. When an individual has no remaining tickets they wish to purchase, they leave the line.
The task is to calculate how much time it will take for the person in position k
(using 0-based indexing) in the line to complete all their ticket purchases.
Intuition
To determine the total time required for the kth
person to buy all their tickets, we have to simulate the ticket-buying process, respecting each person in the line. The main insights for the solution are:
-
Every person in the line, including person
k
, will buy tickets in rounds. In each round, every person, starting from the front of the line, will buy one ticket if they still want to purchase tickets and then go to the end of the line. -
A person will leave the line as soon as they have no tickets left to buy.
-
The person at the
kth
position will buy their last ticket and leave the line, and will not go to the end of the line again.
Based on these points, the solution iterates over each person in the queue:
-
For people ahead of or at position
k
, thekth
person will have to wait for each one of them to buy tickets up to the number of tickets personk
wants (as both will get to buy their tickets). The minimum betweentickets[k]
(the number of tickets personk
wants) andtickets[i]
(the number of tickets the current person wants) is added to the total time. -
For people behind position
k
, thekth
person will wait for each one of them to buy tickets only up to one less than the number of tickets they want (because after thekth
person buys their last ticket, they will leave and not wait for these people anymore). Hence, the minimum betweentickets[k] - 1
(one less than the ticketsk
wants, becausek
won't buy a ticket after the final one) andtickets[i]
is added to the total time.
The sum of all these minimums gives the total time taken for the person at position k
to finish buying their tickets.
Learn more about Queue patterns.
Solution Approach
The given solution follows a straightforward approach without the need for complex algorithms or data structures. The logic simply simulates the purchasing of tickets person by person. Here's a more detailed breakdown:
-
Initialize
ans
to zero, which will accumulate the total time required for thekth
person to buy their tickets. -
Loop through each person in the
tickets
array usingenumerate
, which provides both the indexi
and the number of ticketst
that person wants.-
For a person at or before the
kth
person in the queue (i <= k
): Add the minimum oftickets[k]
andt
toans
. This represents thekth
person waiting for each of the people in front of them, including themselves, to buy up to the same number of tickets that thekth
person wants since they will all get to that number of tickets purchased before thekth
person finishes. -
For a person after the
kth
person in the queue (i > k
): Add the minimum oftickets[k] - 1
andt
toans
. This represents thekth
person waiting for each of the people behind them to buy their tickets, but only up until the point just beforek
buys their last ticket. Since thekth
person won't queue again after buying their last ticket, they won't wait for any tickets bought by the people behind them this final time around.
-
-
After the loop finishes,
ans
holds the total time taken for the person at positionk
to buy all their tickets, and that value is returned.
This solution ensures that the time the kth
person will wait for others is correctly accounted for, adjusting for when they and the people in line ahead of them will buy tickets, and when they won't be in line anymore after buying their last ticket which is why they wait for one ticket less from those behind them. It's a clear and efficient way to simulate the queue process without the need for actual queue manipulation or any additional space, resulting in an O(n) time complexity where n is the number of people in the queue.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example to illustrate the solution approach:
Suppose there are 5 individuals in a line (so n = 5
) meaning to purchase tickets and their respective tickets are the number of tickets they want to buy represented by an array tickets = [1, 2, 5, 2, 1]
. We want to find out how long it will take for the 3rd person (k = 2
, 0-indexed) to buy all of their tickets.
Here is a step-by-step simulation following the solution approach:
-
Initialization:
ans
starts at 0. -
First Pass (i = 0, t = 1, k = 2): The first person wants 1 ticket, which is less than what the 3rd person wants, so we add 1 to
ans
.ans = 1
. -
Second Pass (i = 1, t = 2, k = 2): The second person wants 2 tickets, which is less than what the 3rd person wants, so we add 2 to
ans
.ans = 1 + 2 = 3
. -
Third Pass (i = 2, t = 5, k = 2): The third person is the person in question, they want 5 tickets, so they will buy all their tickets. Add 5 to
ans
.ans = 3 + 5 = 8
. -
Fourth Pass (i = 3, t = 2, k = 2): The fourth person wants 2 tickets. Since the 3rd person will not queue after buying their fifth ticket, we add min(5 - 1, 2) to
ans
, which is 2.ans = 8 + 2 = 10
. -
Fifth Pass (i = 4, t = 1, k = 2): The fifth person wants 1 ticket, which is again less than what the 3rd person wants minus one, so we add 1 to
ans
.ans = 10 + 1 = 11
.
After going through all individuals in the line:
-
For individuals ahead of or at position
k
(the 3rd person), we added the minimum of the number of tickets they want and the number of tickets the 3rd person wants toans
. -
For individuals behind position
k
, we added the minimum of one less than the number of tickets the 3rd person wants and the number of tickets they want toans
.
The total time the 3rd person will wait is ans = 11
. Hence, the 3rd person will take 11 seconds to buy all of their tickets.
Solution Implementation
1from typing import List
2
3class Solution:
4 def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
5 # Initialize the total time required to 0
6 total_time = 0
7
8 # Iterate over the ticket queue to simulate the time passing
9 for index, tickets_at_this_position in enumerate(tickets):
10 # If the current position is before or at the target position k
11 if index <= k:
12 # Add the minimum of the target tickets and tickets at the current position
13 # It ensures we do not count the extra tickets the target person doesn't need
14 total_time += min(tickets[k], tickets_at_this_position)
15 else:
16 # After the target person has bought their tickets, they will not buy more
17 # Thus, for the people after the target, we consider one less ticket for the target
18 # Person at position k would have already bought their ticket when turn comes to later positions
19 total_time += min(tickets[k] - 1, tickets_at_this_position)
20
21 # Return the calculated total time
22 return total_time
23
24# Example usage:
25# sol = Solution()
26# print(sol.timeRequiredToBuy([2, 3, 2], 2)) # This would output 6, the total time to buy tickets
27
1class Solution {
2
3 /**
4 * Calculate the time required for a person to buy tickets.
5 *
6 * @param tickets Array representing the number of tickets each person in the queue needs.
7 * @param k Index of the person whose time to buy tickets is being calculated.
8 * @return The time required for the person at index k to buy their tickets.
9 */
10 public int timeRequiredToBuy(int[] tickets, int k) {
11 // Initialize the answer variable to store the total time required.
12 int totalTime = 0;
13
14 // Loop through each person in the tickets array.
15 for (int i = 0; i < tickets.length; i++) {
16 // If the current person is before or at the position k in the queue,
17 // they will buy tickets[i] amount or the same amount as the person
18 // at the position k, whichever is smaller.
19 if (i <= k) {
20 totalTime += Math.min(tickets[k], tickets[i]);
21 } else {
22 // If the current person is after the position k in the queue,
23 // they can only buy till tickets[k] - 1 as the person at k
24 // will buy their last ticket before them.
25 totalTime += Math.min(tickets[k] - 1, tickets[i]);
26 }
27 }
28
29 // Return the total time required for the person at index k to buy their tickets.
30 return totalTime;
31 }
32}
33
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Calculates the time required to buy tickets
7 int timeRequiredToBuy(vector<int>& tickets, int k) {
8 int totalTime = 0; // Initialize the total time to 0
9 int n = tickets.size(); // Get the number of people in the line
10
11 for (int i = 0; i < n; ++i) {
12 if (i <= k) {
13 // If the person is before or at position k, only buy until the
14 // number of tickets the kth person needs
15 totalTime += min(tickets[k], tickets[i]);
16 } else {
17 // If the person is after the kth person, they can only buy until
18 // one less than the number of tickets the kth person needs, because
19 // when the kth gets their last ticket, these ones can't buy any more.
20 totalTime += min(tickets[k] - 1, tickets[i]);
21 }
22 }
23 return totalTime; // Return the total time calculated
24 }
25};
26
1function timeRequiredToBuy(tickets: number[], k: number): number {
2 const totalPeople = tickets.length;
3 let ticketsForTarget = tickets[k] - 1; // Subtract 1 because the target will purchase their last ticket in the end
4 let totalTime = 0; // Initialize the total time needed
5
6 // Round 1: Everyone purchases tickets up to the number of tickets the target person needs minus one
7 for (let i = 0; i < totalPeople; i++) {
8 if (tickets[i] <= ticketsForTarget) {
9 totalTime += tickets[i]; // Add the number of tickets each person can buy without exceeding target
10 tickets[i] = 0; // They have no more tickets to buy
11 } else {
12 totalTime += ticketsForTarget; // They can only buy as many as the target needs minus one
13 tickets[i] -= ticketsForTarget; // Subtract the bought tickets from their total needed tickets
14 }
15 }
16
17 // Round 2: Continue the purchasing process for remaining tickets
18 // this time including the target person buying their last ticket
19 for (let i = 0; i <= k; i++) {
20 if (tickets[i] > 0) {
21 totalTime += 1; // Add one extra time unit for every person including and before the target
22 }
23 }
24
25 return totalTime;
26}
27
Time and Space Complexity
Time Complexity
The time complexity of the function is O(n)
, where n
is the length of the tickets
array. This is because the function contains a single loop over the tickets
array, and the operations within the loop are constant-time computations, involving simple arithmetic and comparison.
Space Complexity
The space complexity of the function is O(1)
because it uses a fixed amount of extra space ā the ans
variable for storing the cumulative time. No additional data structures are used that grow with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first