# 09.04.2024 [2073. Time Needed to Buy Tickets]
Seconds to buy tickets by `k`-th person in a rotating 1 second queue #easy
09.04.2024
2073. Time Needed to Buy Tickets easy
blog post
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]
until 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()
}