Time Needed to Buy Tickets

Easy
391.

Time Needed to Buy Tickets

Time Needed to Buy Tickets is an easy coding problem on arrays, simulation and queue, asked in Amazon, Adobe and Twitter interviews.

People stand in a queue; tickets[i] is the number of tickets person i still wants. Buying one ticket takes exactly one second. After buying one ticket a person goes to the back of the queue, unless they are done, in which case they leave.

Return the number of seconds it takes the person at position k to buy all of their tickets.

Example 1

Input
tickets = [2,3,2], k = 2
Output
6

Example 2

Input
tickets = [5,1,1,1], k = 0
Output
8

Example 3

Input
tickets = [1], k = 0
Output
1

Constraints

  • 1 <= tickets.length <= 40
  • 1 <= tickets[i] <= 100
  • 0 <= k < tickets.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} tickets
 * @param {number} k
 * @return {number}
 */
var timeRequiredToBuy = function(tickets, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Time Needed to Buy Tickets — Solution in Python, Java & C++

Time Needed to Buy Tickets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Time Needed to Buy Tickets is an easy coding problem on arrays, simulation and queue, asked in Amazon, Adobe and Twitter interviews.

  • Difficulty: Easy
  • Topics: Arrays, Simulation, Queue
  • Asked at: Amazon, Adobe, Twitter
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

People stand in a queue; tickets[i] is the number of tickets person i still wants. Buying one ticket takes exactly one second. After buying one ticket a person goes to the back of the queue, unless they are done, in which case they leave.

Return the number of seconds it takes the person at position k to buy all of their tickets.

Example 1

Input: tickets = [2,3,2], k = 2
Output: 6

Example 2

Input: tickets = [5,1,1,1], k = 0
Output: 8

Example 3

Input: tickets = [1], k = 0
Output: 1

Constraints

  • 1 <= tickets.length <= 40
  • 1 <= tickets[i] <= 100
  • 0 <= k < tickets.length

Hints for Time Needed to Buy Tickets

  1. Hint 1

    Simulating the queue works, but each person's contribution can be counted directly.

  2. Hint 2

    Someone at or before k buys at most tickets[k] tickets before person k finishes.

  3. Hint 3

    Someone after k gets one fewer round, so they contribute at most tickets[k] - 1.

How to solve Time Needed to Buy Tickets

Count each person's contribution directly: someone at or before k buys at most tickets[k] before k finishes, someone after k at most tickets[k] - 1.

Approach

  1. Sum min(tickets[i], tickets[k]) for i <= k and min(tickets[i], tickets[k] - 1) for i > k.

Why it works

Person k finishes during their tickets[k]-th round; everyone ahead has had exactly that many turns, everyone behind one fewer.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Simulating the queue is also correct but O(n · max(tickets)).

Reference solution

Python

def timeRequiredToBuy(tickets, k: int) -> int:
    time = 0
    for i, want in enumerate(tickets):
        if i <= k:
            time += min(want, tickets[k])
        else:
            time += min(want, tickets[k] - 1)
    return time

Java

public static int timeRequiredToBuy(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;
}

C++

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

JavaScript

var timeRequiredToBuy = function(tickets, k) {
    let time = 0;
    for (let 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;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Queues and Deques