algoadvance

Leetcode 2073. Time Needed to Buy Tickets

Problem Statement

You are given an array tickets where tickets[i] represents the number of tickets that the i-th person needs. Each person can buy only one ticket at a time in a round-robin fashion until they have all their tickets.

Return the time needed to buy all tickets for the k-th person, who is standing in the queue.

Clarifying Questions

  1. Does every person buy a ticket per unit time?
    • Yes, every person takes one unit time to buy one ticket.
  2. Is the k-th person’s index 0-based or 1-based?
    • The index is 0-based.
  3. What happens when a person has bought all their tickets?
    • They leave the queue and do not need to wait for the remaining rounds.

Strategy

  1. Initialize a time counter to track the total time taken.
  2. Traverse the queue in a round-robin manner.
  3. For each person, decrement the number of tickets they need by 1 and increment the time counter.
  4. Stop the process as soon as the k-th person buys their last ticket.

Code

Here’s how you could implement the solution in C++:

#include <vector>
#include <iostream>

class Solution {
public:
    int timeRequiredToBuy(std::vector<int>& tickets, int k) {
        int time = 0;
        
        // Iterate over tickets until the k-th person buys their last ticket
        while (tickets[k] > 0) {
            for(int i = 0; i < tickets.size(); ++i) {
                if (tickets[i] > 0) {
                    // Person i buys a ticket
                    tickets[i]--;
                    time++;
                    
                    // Check if it was the k-th person's last ticket
                    if (i == k && tickets[k] == 0) {
                        return time;
                    }
                }
            }
        }
        
        return time;
    }
};

int main() {
    Solution sol;
    std::vector<int> tickets = {2, 3, 2};
    int k = 2;
    std::cout << "Time needed: " << sol.timeRequiredToBuy(tickets, k) << "\n";
    return 0;
}

Time Complexity

The time complexity is (O(N * T)), where (N) is the number of people in the queue, and (T) is the maximum number of tickets any single person needs to buy. This is because, in the worst case, we could be iterating once for each ticket every person has.

In practical scenarios, this ensures the algorithm efficiently handles the round-robin mechanism until the k-th person completes their purchase.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI