LeetCode Entry

2073. Time Needed to Buy Tickets

09.04.2024 easy 2024 kotlin rust

Seconds to buy tickets by k-th person in a rotating 1 second queue

2073. Time Needed to Buy Tickets easy blog post substack youtube 2024-04-09_08-27.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/565

Problem TLDR

Seconds to buy tickets by k-th person in a rotating 1 second queue #easy

Intuition

The brute-force implementation is trivial: just repeat decreasing tickets[i] untile tickets[k] == 0. It will take at most O(n^2) time.

However, there is a one-pass solution. To get the intuition go to the comment section… just a joke. We take tickets[k] for people before k and we don’t take last round tickets for people after k, so only tickets[k] - 1.

Approach

Let’s use some iterators to reduce the number of lines of code: sumOf, withIndex or iter().enumerate(),

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun timeRequiredToBuy(tickets: IntArray, k: Int) =
        tickets.withIndex().sumOf { (i, t) ->
            min(tickets[k] - (if (i > k) 1 else 0), t)
    }



    pub fn time_required_to_buy(tickets: Vec<i32>, k: i32) -> i32 {
        tickets.iter().enumerate().map(|(i, &t)|
            t.min(tickets[k as usize] - i32::from(i > k as usize))).sum()
    }