Time Needed to Buy Tickets

 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.

 

    Summary of Logic:

  • Put all people in a queue (we use their index).

  • Keep letting the front person buy 1 ticket at a time.

  • Count time for each ticket bought.

  • Re-insert person to queue if they still need tickets.

  • Stop when person at index k has 0 tickets left.

🧠 Simple Explanation:

  • We keep going person by person.

  • Every time someone buys a ticket, it takes 1 second.

  • If that person still needs tickets, they go to the back.

  • Stop when the person at position k has 0 tickets left.

     Dry Run (tickets = [2,3,2], k = 2)

    Queue: [0,1,2]

    • 0 → buys → [1,1,2] → back

    • 1 → buys → [1,2,2] → back

    • 2 → buys → [1,2,1] → back

    • 0 → buys → [0,2,1]

    • 1 → buys → [0,1,1] → back

    • 2 → buys → [0,1,0] → done 

    Time = 6


class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {

        // Create a queue to store the indices of people in line
        Queue<Integer> que = new LinkedList<>();
        int n = tickets.length;

        // Add all people (indices from 0 to n-1) to the queue
        for (int i = 0; i < n; i++) {
            que.offer(i);
        }

        int time = 0;

        // Run the loop until the person at position 'k' has no tickets left
        while (tickets[k] > 0) {
            // Get the person at the front of the queue
            int front = que.poll();

            // If the person still has tickets left
            if (tickets[front] > 0) {
                tickets[front]--; // They buy 1 ticket
                time++; // Time increases by 1 second

                // If they still need more tickets, go back to the end of the queue
                if (tickets[front] > 0) {
                    que.offer(front);
                }
            }
        }

        // Return total time taken for person at index 'k' to buy all tickets
        return time;
    }
}

Comments

Post a Comment

Popular posts from this blog

Two Sum II - Input Array Is Sorted

 Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order , find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice. Your solution must use only constant extra space .   Example 1: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2]. Example 2: Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3]. Example 3: Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1,...
Read more

Comparable Vs. Comparator in Java

  In Java , Comparable and Comparator both are interfaces used to sort objects. Comparable It defines  natural ordering  within a class. It is implemented  inside  the class being sorted. It uses the compareTo() method. It allows sorting  by one one . Comparable provides a  single sorting sequence . In other words, we can sort the collection on the basis of a single element such as id, name, and price. Comparable  affects the original class , i.e., the actual class is modified. Comparable is present in  java.lang  package. We can sort the list elements of Comparable type by  Collections.sort(List)  method. Only one compareTo() method can be implemented, restricting flexibility. Comparator It defines  custom sorting logic It is implemented  in a separate class  or using lambda expressions . It uses the compare() method. It allows sorting  by multiple criteria . The Comparator provides  multiple sorting...
Read more

Increasing Triplet Subsequence

 Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.   Example 1: Input: nums = [1,2,3,4,5] Output: true Explanation: Any triplet where i < j < k is valid. Example 2: Input: nums = [5,4,3,2,1] Output: false Explanation: No triplet exists. Example 3: Input: nums = [2,1,5,0,4,6] Output: true Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6. Brute Force : Failed for some testcase class Solution {     public boolean increasingTriplet ( int [] nums ) {         int n = nums . length ;         int i = 0 ;         int j =i+ 1 ;         int k =j+ 1 ;         while (i <n && j<n && k<n)         {         if (nums...
Read more