Scale Engineer

Time Needed to Buy Tickets

Easy
#1887Time: O(N * max(tickets)). In the worst case, the person at `k` needs `tickets[k]` passes through the line. In each pass, there are at most `N` people. Thus, the total time is proportional to the product of the number of people and the number of tickets.Space: O(N), where N is the number of people. This is for the queue which stores the indices of the people in line.2 companies
Data structures
ArrayQueue
Companies
XKomprise

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the ticket-buying process as described in the problem. We use a queue to represent the line of people. Each person buys a ticket, and if they need more, they are sent to the back of the queue. We keep track of the elapsed time until the person at index k has bought all their tickets.

Algorithm

  • Create a Queue and populate it with the indices of people, from 0 to n-1.
  • Initialize a time variable to 0.
  • Start a loop that continues as long as the person at index k has tickets to buy.
  • Inside the loop, dequeue the person's index p from the front of the queue.
  • Increment the time counter.
  • Decrement the ticket count for person p.
  • If person p is the target person (p == k) and they have just finished buying tickets (tickets[p] == 0), return the total time.
  • If person p still needs more tickets (tickets[p] > 0), add their index p back to the end of the queue.

Walkthrough

The most intuitive way to solve this problem is to replicate the process exactly. We can use a queue, a data structure that perfectly models a first-in, first-out line.

  1. Initialization: We start by creating a queue and adding the initial indices of all people (0, 1, ..., n-1) into it. We also initialize a time counter to zero.
  2. Simulation Loop: The simulation runs in a loop. In each iteration, we simulate one second of time:
    • We take the person at the front of the queue (by dequeuing their index).
    • We increment our time counter.
    • This person buys one ticket, so we decrement their required ticket count in the tickets array.
    • We then check if this person was our target person at index k and if they have now bought all their tickets. If so, the simulation is over, and we return the current time.
    • If the person still has tickets to buy, they go to the back of the line, which we simulate by enqueuing their index.
    • If a person finishes buying all their tickets (and they are not the person at index k whose completion would stop the process), they simply leave the line and are not added back to the queue.

This process continues until the person at index k buys their last ticket.

import java.util.LinkedList;import java.util.Queue; class Solution {    public int timeRequiredToBuy(int[] tickets, int k) {        Queue<Integer> queue = new LinkedList<>();        for (int i = 0; i < tickets.length; i++) {            queue.add(i);        }         int time = 0;        // The loop continues as long as the queue is not empty.        // The condition to stop is checked inside the loop.        while (!queue.isEmpty()) {            int personIndex = queue.poll();            time++;            tickets[personIndex]--;             if (personIndex == k && tickets[k] == 0) {                return time;            }             if (tickets[personIndex] > 0) {                queue.add(personIndex);            }        }        return time; // Should not be reached given problem constraints    }}

Complexity

Time

O(N * max(tickets)). In the worst case, the person at `k` needs `tickets[k]` passes through the line. In each pass, there are at most `N` people. Thus, the total time is proportional to the product of the number of people and the number of tickets.

Space

O(N), where N is the number of people. This is for the queue which stores the indices of the people in line.

Trade-offs

Pros

  • Straightforward to understand as it directly models the real-world process.

  • Correctly handles the state of the queue at every second.

Cons

  • Less efficient compared to other approaches, with a time complexity dependent on the number of tickets.

  • Uses extra space for the queue, which can be up to O(n).

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem