2073. Time Needed to Buy Tickets - Solution

The problem

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

Approach overview

Problem Overview: An array tickets represents how many tickets each person in a queue wants to buy. Each second, the person at the front buys one ticket and moves to the back if they still need more. The process stops when the person at index k finishes buying all their tickets. The goal is to compute the total time required.

Approach 1: Simulation with Queue (Time: O(sum(tickets)), Space: O(n))

This approach directly models the queue behavior. Push each person’s index and remaining ticket count into a queue and simulate the process second by second. At every step, pop the front person, decrement their ticket count, and if they still need tickets push them back to the queue. Stop once the person at index k buys their final ticket. The logic mirrors the real-world process and is easy to reason about. However, the loop may run up to sum(tickets) iterations in the worst case, which can be large if many people want many tickets. This method primarily uses a queue for ordering and simple simulation of events.

Approach 2: Mathematical Reduction (Time: O(n), Space: O(1))

The queue behavior has a predictable pattern that allows counting the time without simulating every second. Each person before or at index k can buy at most tickets[k] tickets before k finishes. Each person after k can buy at most tickets[k] - 1 tickets, because the process stops immediately after k purchases their last ticket. Iterate once through the array and accumulate contributions using min(tickets[i], tickets[k]) for i ≤ k and min(tickets[i], tickets[k] - 1) for i > k. This counts exactly how many seconds each person participates in the buying cycle. The solution runs in linear time with constant space and relies only on simple array iteration.

Recommended for interviews: Start by describing the simulation since it demonstrates understanding of the queue process and matches the problem statement directly. Then optimize to the mathematical counting approach. Interviewers typically expect the O(n) reduction because it removes unnecessary simulation and shows you recognized the purchase pattern across the queue.

Approach 1: Simulation Approach

This approach simulates the process of each person buying their tickets. We keep track of the time spent and decrement the ticket count from each person one at a time until the k-th person has purchased all their tickets.

Python

def time_to_buy_tickets(tickets, k):
    time = 0
    n = len(tickets)
    while True:
        for i in range(n):
            if tickets[i] > 0:
                tickets[i] -= 1
                time += 1
                if i == k and tickets[k] == 0:
                    return time

print(time_to_buy_tickets([2, 3, 2], 2))

Java

public class TicketBuying {
    public static int timeToBuyTickets(int[] tickets, int k) {
        int time = 0;
        int n = tickets.length;
        while (true) {
            for (int i = 0; i < n; i++) {
                if (tickets[i] > 0) {
                    tickets[i]--;
                    time++;
                    if (i == k && tickets[k] == 0) return time;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] tickets = {2, 3, 2};
        int k = 2;
        System.out.println("Time taken: " + timeToBuyTickets(tickets, k));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int timeToBuyTickets(vector<int>& tickets, int k) {
    int time = 0;
    for (int i = 0; ; i = (i + 1) % tickets.size()) {
        if (tickets[i] > 0) {
            tickets[i]--;
            time++;
            if (i == k && tickets[k] == 0) return time;
        }
    }
}

int main() {
    vector<int> tickets = {2, 3, 2};
    int k = 2;
    cout << "Time taken: " << timeToBuyTickets(tickets, k) << endl;
    return 0;
}

JavaScript

function timeToBuyTickets(tickets, k) {
    let time = 0;
    const n = tickets.length;
    while (true) {
        for (let i = 0; i < n; i++) {
            if (tickets[i] > 0) {
                tickets[i]--;
                time++;
                if (i === k && tickets[k] === 0) return time;
            }
        }
    }
}

console.log(timeToBuyTickets([2, 3, 2], 2));

#include <stdio.h>

int timeToBuyTickets(int* tickets, int ticketsSize, int k) {
    int time = 0;
    for (int i = 0; ; i = (i + 1) % ticketsSize) {
        if (tickets[i] > 0) {
            tickets[i]--;
            time++;
            if (i == k && tickets[k] == 0) return time;
        }
    }
}

int main() {
    int tickets[] = {2, 3, 2};
    int k = 2;
    printf("Time taken: %d\n", timeToBuyTickets(tickets, 3, k));
    return 0;
}

using System;

class TicketBuying {
    public static int TimeToBuyTickets(int[] tickets, int k) {
        int time = 0;
        int n = tickets.Length;
        while (true) {
            for (int i = 0; i < n; i++) {
                if (tickets[i] > 0) {
                    tickets[i]--;
                    time++;
                    if (i == k && tickets[k] == 0) return time;
                }
            }
        }
    }

    static void Main() {
        int[] tickets = {2, 3, 2};
        int k = 2;
        Console.WriteLine("Time taken: " + TimeToBuyTickets(tickets, k));
    }
}

Python provides a straightforward implementation of the simulation approach. We use a list to track tickets and loop until the k-th person completes their purchases.

Complexity

Time Complexity: O(n * max(tickets))
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Mathematical Reduction Approach

This approach avoids the simulation by calculating the total time taken mathematically. For this, we traverse through each person and calculate the time based on the number of people in the queue and the minimum value between their current tickets and the tickets needed by k-th person.

Python

def time_to_buy_tickets(tickets, k):
    time = 0
    for i in range(len(tickets)):
        if i <= k:
            time += min(tickets[i], tickets[k])
        else:
            time += min(tickets[i], tickets[k] - 1)
    return time

print(time_to_buy_tickets([5, 1, 1, 1], 0))

Java

public class TicketBuying {
    public static int timeToBuyTickets(int[] tickets, int k) {
        int time = 0;
        for (int i = 0; i < tickets.length; i++) {
            if (i <= k) {
                time += Math.min(tickets[i], tickets[k]);
            } else {
                time += Math.min(tickets[i], tickets[k] - 1);
            }
        }
        return time;
    }

    public static void main(String[] args) {
        int[] tickets = {5, 1, 1, 1};
        int k = 0;
        System.out.println("Time taken: " + timeToBuyTickets(tickets, k));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int timeToBuyTickets(vector<int>& tickets, int k) {
    int time = 0;
    for (int i = 0; i < tickets.size(); i++) {
        if (i <= k) {
            time += min(tickets[i], tickets[k]);
        } else {
            time += min(tickets[i], tickets[k] - 1);
        }
    }
    return time;
}

int main() {
    vector<int> tickets = {5, 1, 1, 1};
    int k = 0;
    cout << "Time taken: " << timeToBuyTickets(tickets, k) << endl;
    return 0;
}

JavaScript

function timeToBuyTickets(tickets, k) {
    let time = 0;
    for (let i = 0; i < tickets.length; i++) {
        time += i <= k ? Math.min(tickets[i], tickets[k]) : Math.min(tickets[i], tickets[k] - 1);
    }
    return time;
}

console.log(timeToBuyTickets([5, 1, 1, 1], 0));

#include <stdio.h>

int timeToBuyTickets(int* tickets, int ticketsSize, int k) {
    int time = 0;
    for (int i = 0; i < ticketsSize; i++) {
        if (i <= k) {
            time += tickets[i] < tickets[k] ? tickets[i] : tickets[k];
        } else {
            time += tickets[i] < tickets[k] - 1 ? tickets[i] : tickets[k] - 1;
        }
    }
    return time;
}

int main() {
    int tickets[] = {5, 1, 1, 1};
    int k = 0;
    printf("Time taken: %d\n", timeToBuyTickets(tickets, 4, k));
    return 0;
}

using System;

class TicketBuying {
    public static int TimeToBuyTickets(int[] tickets, int k) {
        int time = 0;
        for (int i = 0; i < tickets.Length; i++) {
            time += i <= k ? Math.Min(tickets[i], tickets[k]) : Math.Min(tickets[i], tickets[k] - 1);
        }
        return time;
    }

    static void Main() {
        int[] tickets = {5, 1, 1, 1};
        int k = 0;
        Console.WriteLine("Time taken: " + TimeToBuyTickets(tickets, k));
    }
}

Python's clarity helps in implementing the mathematical approach, making the calculation of each person's purchase time efficiently.

Complexity

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

Try this approach in the editor

Approach 3: Single Pass

According to the problem description, when the k^{th} person finishes buying tickets, all the people in front of the k^{th} person will not buy more tickets than the k^{th} person, and all the people behind the k^{th} person will not buy more tickets than the k^{th} person minus 1.

Therefore, we can traverse the entire queue. For the i^{th} person, if i leq k, the time to buy tickets is min(tickets[i], tickets[k]); otherwise, the time to buy tickets is min(tickets[i], tickets[k] - 1). We sum the buying time for all people to get the result.

The time complexity is O(n), where n is the length of the queue. The space complexity is O(1).

TypeScript

function timeRequiredToBuy(tickets: number[], k: number): number {
    let ans = 0;
    const n = tickets.length;
    for (let i = 0; i < n; ++i) {
        ans += Math.min(tickets[i], i <= k ? tickets[k] : tickets[k] - 1);
    }
    return ans;
}

func timeRequiredToBuy(tickets []int, k int) (ans int) {
	for i, x := range tickets {
		t := tickets[k]
		if i > k {
			t--
		}
		ans += min(x, t)
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Simulation Approach	Time Complexity: O(n * max(tickets)) Space Complexity: O(1)
Mathematical Reduction Approach	Time Complexity: O(n) Space Complexity: O(1)
Single Pass	–

Complexity analysis

Approach	Time	Space	When to Use
Queue Simulation	O(sum(tickets))	O(n)	When you want a direct model of the process or when explaining the logic step-by-step in interviews
Mathematical Reduction	O(n)	O(1)	Best for production or interview optimization since it counts contributions without simulating each second

Frequently asked questions

Is Time Needed to Buy Tickets easy or hard?

LeetCode classifies Time Needed to Buy Tickets as an Easy problem with an acceptance rate above 70%. The simulation idea is straightforward, while the O(n) optimization introduces a small counting insight.

Time Needed to Buy Tickets Python/Java solution

Both Python and Java implementations typically follow the O(n) counting strategy. Iterate through the array, apply the min(tickets[i], tickets[k]) or min(tickets[i], tickets[k]-1) rule depending on the index, and sum the results to compute the total time.

How to solve Time Needed to Buy Tickets in O(n)?

Iterate through the tickets array and accumulate how many times each person contributes to the buying process. For indices i ≤ k add min(tickets[i], tickets[k]). For indices i > k add min(tickets[i], tickets[k] - 1). The sum of these values gives the total time.

What is the best approach for Time Needed to Buy Tickets?

The mathematical reduction approach is the most efficient. Instead of simulating the queue second by second, it counts how many times each person gets a chance to buy before person k finishes. This reduces the complexity to O(n) time and O(1) space.

Is Time Needed to Buy Tickets asked at Google/Amazon/Meta?

Queue and simulation problems like this commonly appear in interviews at companies such as Amazon and Google. The question tests reasoning about queue behavior, counting patterns, and the ability to optimize a simulation into a mathematical solution.

What data structure is used in Time Needed to Buy Tickets?

The direct approach uses a queue to simulate people cycling through the ticket line. The optimized solution does not require additional data structures and instead relies on simple array iteration and counting.

What is the time complexity of Time Needed to Buy Tickets?

The optimal solution runs in O(n) time and O(1) space by iterating through the array once and counting how many tickets each person can buy before index k completes their purchases. A straightforward simulation approach takes O(sum(tickets)) time.

Time Needed to Buy Tickets solution and explanation

The problem

Approach overview

Approach 1: Simulation Approach

Approach 2: Mathematical Reduction Approach

Approach 3: Single Pass

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Time Needed to Buy Tickets solution and explanation

The problem

Approach overview

Approach 1: Simulation Approach

Approach 2: Mathematical Reduction Approach

Approach 3: Single Pass

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems