medium Minimum Number of Coins for Fruits

Problem Statement

You are given an array of integers prices where each element prices[i] represents the number of coins required to buy the i^th fruit.

The fruit market has the following reward for each fruit:

• If you buy the i^th fruit for prices[i] coins, you can get the next (i + 1) fruits for free.

Note: Even if you have the option to take certain fruits for free, you can still choose to purchase them at their respective prices[j] to gain the reward for the next fruits.

Return the minimum number of coins needed to get all the fruits.

Examples

Example 1:

• Input: prices = [1, 6, 1, 2, 4]
• Expected Output: 2
• Explanation:
  • Purchase the first fruit for 1 coin. Get next i + 1 = 0 + 1 = 1 fruit for free.
  • Get a second fruit for free.
  • Purchase the third fruit for 1 coin, and get next i + 1 = 2 + 1 = 3 fruits for free.
  • Get fourth and fifth fruit for free.
  • Total cost = 1 + 1 = 2.

Example 2:

• Input: prices = [2, 3, 5, 1]
• Expected Output: 5
• Explanation:
  • Purchase the first fruit for 2 coins. This allows you to take the second fruit for free.
  • You get 2nd fruit for free, but still, purchase it with 3 coins to get the third and fourth fruit for free.
  • So, total cost = 2 + 3 = 5.

Example 3:

• Input: prices = [3, 2, 1, 4]
• Expected Output: 4
• Explanation:
  • Purchase the first fruit for 3 coins. Get next i + 1 = 0 + 1 = 1 fruit for free.
  • Get a second fruit for free.
  • Purchase the third fruit for 1 coin, and get next i + 1 = 2 + 1 = 3 fruits for free.
  • Get fourth fruit for free.
  • Total cost = 3 + 1 = 4.

Constraints:

• 1 <= prices.length <= 1000
• 1 <= prices[i] <= 10⁵

Solution

To solve the problem of finding the minimum number of coins needed to purchase all the fruits, we use a technique that involves iterating through the fruit prices from the last one to the first. By doing this, we can determine the most cost-effective way to buy each fruit and any subsequent fruits that might be available for free as a reward. We keep track of the best options using a deque (a double-ended queue) that helps us efficiently manage which fruits to consider for minimizing the total cost.

The deque is used to store the indices of the fruits in a way that allows us to quickly find the minimum cost for any given range of fruits. As we iterate through the prices, we update each fruit’s cost to include the cheapest possible way to get all the subsequent fruits. By the end of the loop, the total minimum cost to purchase all fruits is stored in the first element of the prices array, which is then returned as the result. This approach is both efficient and straightforward, ensuring we achieve the optimal solution.

Step-by-Step Algorithm

1. Initialize Variables:

   • Determine the number of fruits, n, by finding the length of the prices array.
   • Create a deque, deque, which will help in tracking the minimum prices efficiently as we move backward through the array.

2. Extend Prices Array:

   • Extend the prices array by one element to avoid boundary issues when accessing future fruits.
   • Set the last element, prices[n], to 0 because no additional cost is required after the last fruit.

3. Start Iteration:

   • Begin iterating through the prices array from the last fruit to the first. The loop runs from i = n - 1 to i = 0.

4. Calculate Maximum Covered Index:

   • For each fruit i, calculate the maximum index that can be covered by buying this fruit. This is computed as maxCoveredIndex = min(n, 2 * i + 2), which ensures we don't go beyond the array bounds.

5. Manage the Deque:

   • Remove Out of Range Elements: While the front of the deque contains indices greater than maxCoveredIndex, remove those elements. This ensures the deque only contains relevant indices that fall within the range of the current fruit's reward.
   • Update Current Fruit Cost: Add the minimum cost of the next fruit in the deque to the current fruit's cost: prices[i] += prices[deque.peekFirst()]. This updates the price of the current fruit to include the best possible price for acquiring future fruits.
   • Maintain Deque Order: While the deque is not empty and the cost of the current fruit is less than the cost of the fruit at the back of the deque, remove elements from the back of the deque. This ensures that the deque always remains sorted in increasing order of prices.

6. Add Current Fruit Index to Deque:

   • Add the current index i to the deque using deque.addLast(i). This ensures that the deque will be considered for future fruits.

7. Return the Minimum Coins:

   • After the loop ends, the minimum coins required to get all fruits starting from the first one is stored in prices[0]. Return this value.

Algorithm Walkthrough

Let's walk through the algorithm step by step with the input prices = [1, 6, 1, 2, 4].

1. Initial Setup:

   • Start with prices = [1, 6, 1, 2, 4] and deque = [].
   • Append 0 to prices to avoid boundary issues, so prices = [1, 6, 1, 2, 4, 0].
   • Push n = 5 to deque, so deque = [5].

2. Iteration 1 (i = 4):

   • Calculate maxCoveredIndex = Math.min(5, 2 * 4 + 2) = 5.
   • No elements to remove from deque since deque[0] = 5 is within range.
   • Update prices[4]: prices[4] = 4 + prices[5] = 4 + 0 = 4.
   • No elements to remove from the back of deque since prices[i] < prices[deque[deque.length - 1]] (4 < 0) is not true.
   • Push 4 to deque, so deque = [5, 4].

3. Iteration 2 (i = 3):

   • Calculate maxCoveredIndex = Math.min(5, 2 * 3 + 2) = 5.
   • No elements to remove from deque since deque[0] = 5 is within range.
   • Update prices[3]: prices[3] = 2 + prices[5] = 2 + 0 = 6.
   • Remove 4 from deque as prices[3] < prices[4].
   • Push 3 to deque, so deque = [5, 3].

4. Iteration 3 (i = 2):

   • Calculate maxCoveredIndex = Math.min(5, 2 * 2 + 2) = 5.
   • No elements to remove from deque since deque[0] = 5 is within range.
   • Update prices[2]: prices[2] = 1 + prices[5] = 1 + 0 = 1.
   • Remove 3 from deque as prices[2] < prices[3].
   • Push 2 to deque, so deque = [5, 2].

5. Iteration 4 (i = 1):

   • Calculate maxCoveredIndex = Math.min(5, 2 * 1 + 2) = 4.
   • Remove 5 from deque since deque[0] = 5 is out of range. Now, deque = [2]
   • Update prices[1]: prices[1] = 6 + prices[2] = 6 + 1 = 7.
   • No elements are required to remove from the back.
   • Push 1 to deque, so deque = [2, 1].

6. Iteration 5 (i = 0):

   • Calculate maxCoveredIndex = Math.min(5, 2 * 0 + 2) = 2.
   • No elements to remove from deque since deque[0] = 2 is within range.
   • Update prices[0]: prices[0] = 1 + prices[2] = 1 + 1 = 2.
   • Push 0 to deque, so deque = [2, 0].

7. Final Output:

   • After all iterations, prices[0] is 2, which is the minimum cost to buy all fruits.

Code

import java.util.*;

class Solution {

  public int minimumCoins(int[] prices) {
    int n = prices.length;
    Deque<Integer> deque = new LinkedList<>();
    deque.addLast(n);
    prices = Arrays.copyOf(prices, n + 1);
    prices[n] = 0; // Add a dummy fruit with 0 coins to avoid boundary issues.

    // Iterate from the last fruit to the first
    for (int i = n - 1; i >= 0; i--) {
      // Calculate the maximum index that can be covered by the current fruit
      int maxCoveredIndex = Math.min(n, 2 * i + 2);

      // Remove all elements from the front that are outside the range of current fruit's reward
      while (!deque.isEmpty() && deque.peekFirst() > maxCoveredIndex) {
        deque.pollFirst();
      }

      // Update the cost of the current fruit by adding the minimum cost of reachable fruits
      prices[i] += prices[deque.peekFirst()];

      // Maintain the deque to keep it increasing
      while (!deque.isEmpty() && prices[i] < prices[deque.peekLast()]) {
        deque.pollLast();
      }

      // Add the current fruit index to the deque
      deque.addLast(i);
    }

    // Return the minimum cost to get all fruits starting from the first one
    return prices[0];
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] prices1 = { 1, 6, 1, 2, 4 };
    System.out.println("Example 1: " + solution.minimumCoins(prices1)); // Expected Output: 2

    // Example 2
    int[] prices2 = { 2, 3, 5, 1 };
    System.out.println("Example 2: " + solution.minimumCoins(prices2)); // Expected Output: 5

    // Example 3
    int[] prices3 = { 3, 2, 1, 4 };
    System.out.println("Example 3: " + solution.minimumCoins(prices3)); // Expected Output: 4
  }
}

Complexity Analysis

Time Complexity

• Deque operations: Each index is pushed and popped from the deque at most once, making the time complexity for deque operations .
• Main Loop: The main loop iterates over each element of the prices array exactly once, which is .

Overall, the time complexity of the algorithm is , where n is the number of elements in the prices array.

Space Complexity

• Deque: The space used by the deque is proportional to the number of elements it holds at any time, which is in the worst case.
• Auxiliary Space: An extra space is used to store the extended prices array, but this is also .

Overall, the space complexity of the algorithm is .