2073. Time Needed to Buy Tickets

Time Needed to Buy Tickets 

Problem Description

This is an easy problem where we can just implement what the problem describes. This means we will need to create the queue & simulate the ticket buying process while keeping track of the time. 

There are n people in a line queuing to buy tickets, where the 0th a person is at the front of the line and the (n - 1)th a 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 a 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 in a position k (0-indexed) to finish buying tickets.

 

Example 1:

Input: tickets = [2,3,2], k = 2
Output: 6
Explanation: 
- In the first pass, everyone in the line buys a ticket and the line becomes [1, 2, 1].
- In the second pass, everyone in the line buys a ticket and the line becomes [0, 1, 0].
The person at position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds.

Example 2:

Input: tickets = [5,1,1,1], k = 0
Output: 8
Explanation:
- In the first pass, everyone in the line buys a ticket and the line becomes [4, 0, 0, 0].
- In the next 4 passes, only the person in position 0 is buying tickets.
The person at position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds.

 

Constraints:

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

Here we are going to discuss two ways to solve this problem using javascript 

• Brute Force (Queue)
• One Liner (Using reduce - Inbuilt function)

Approach A)

/**
 * @param {number[]} tickets
 * @param {number} k
 * @return {number}
 */
var timeRequiredToBuy = function(tickets, k) {
    let count = 0;
    while(tickets[k] > 0){
        for(let i=0;i<tickets.length;i++){
            if(tickets[k] == 0){
               return count;
            }
            if(tickets[i] > 0){
                count++;
                tickets[i]--;
            }
        }
        if(tickets[k] == 0){
            break;
        }
    }
    return count;
};

Complexity analysis.

Time Complexity

    We are traversing through the complete array which needs O(N²).

Space Complexity

    We are using count as a constant, hence space complexity is O(1).

Approach B)

/**
 * @param {number[]} tickets
 * @param {number} k
 * @return {number}
 */
var timeRequiredToBuy = function(tickets, k) {
    return tickets.reduce((x, v, i)=>x + Math.min(v, tickets[k] - (i > k)), 0);
};

Complexity analysis.

Time Complexity

    We are traversing through the complete array which needs O(N).

Space Complexity

    We are not using any extra space here

Resources:

https://github.com/PraveenMistry/leetCode

https://medium.com/@praveenmistry/queue-javascript-part-2-5dab626110aa

Conclusion

That’s all folks! In this post, we solved LeetCode problem #2073. Time Needed to Buy Tickets 

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!