Minimum number of coins for fruits ii

Array Dynamic Programming Queue Heap (Priority Queue) Monotonic Queue

47.3% acceptance

Mar 31, 2026

You are at a fruit market with different types of exotic fruits on display. You are given a 1-indexed array prices, where prices[i] denotes the number of coins needed to purchase the ith fruit. The fruit market has the following offer: If you purchase the ith fruit at prices[i] coins, you can get the next i fruits for free. Note that even if you can take fruit j for free, you can still purchase it for prices[j] coins to receive a new offer. Return the minimum number of coins needed to acquire all the fruits.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_coins(prices: Vec<i32>) -> i32 {
    let n = prices.len();
    let mut dp = vec![0i32; n + 2];
    let mut deque: std::collections::VecDeque<(usize, i32)> = std::collections::VecDeque::new();
    for i in (1..=n).rev() {
      let j = i + 1;
      let dpj = dp[j];
      while !deque.is_empty() && deque.back().unwrap().1 >= dpj {
        deque.pop_back();
      }
      deque.push_back((j, dpj));
      while !deque.is_empty() && deque.front().unwrap().0 > 2 * i + 1 {
        deque.pop_front();
      }
      dp[i] = prices[i - 1] + deque.front().unwrap().1;
    }
    dp[1]
  }
}