Watch 10 video solutions for Collecting Chocolates, a medium level problem involving Array, Enumeration. This walkthrough by Prakhar Agrawal has 2,181 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums of size n representing the cost of collecting different chocolates. The cost of collecting the chocolate at the index i is nums[i]. Each chocolate is of a different type, and initially, the chocolate at the index i is of ith type.
In one operation, you can do the following with an incurred cost of x:
ith type to ((i + 1) mod n)th type for all chocolates.Return the minimum cost to collect chocolates of all types, given that you can perform as many operations as you would like.
Example 1:
Input: nums = [20,1,15], x = 5 Output: 13 Explanation: Initially, the chocolate types are [0,1,2]. We will buy the 1st type of chocolate at a cost of 1. Now, we will perform the operation at a cost of 5, and the types of chocolates will become [1,2,0]. We will buy the 2nd type of chocolate at a cost of 1. Now, we will again perform the operation at a cost of 5, and the chocolate types will become [2,0,1]. We will buy the 0th type of chocolate at a cost of 1. Thus, the total cost will become (1 + 5 + 1 + 5 + 1) = 13. We can prove that this is optimal.
Example 2:
Input: nums = [1,2,3], x = 4 Output: 6 Explanation: We will collect all three types of chocolates at their own price without performing any operations. Therefore, the total cost is 1 + 2 + 3 = 6.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1091 <= x <= 109Problem Overview: You have n types of chocolates where nums[i] is the cost of collecting type i. You can perform a rotation operation that shifts types and costs x. The goal is to collect every type with the minimum total cost by choosing the best moment (after some rotations) to collect each chocolate.
Approach 1: Simulate Operations and Calculate Costs (O(n^2) time, O(n) space)
Simulate each possible number of rotations from 0 to n-1. After k rotations, chocolate type i can be bought from position (i + k) % n. Track the minimum price seen so far for every chocolate type using an auxiliary array. For each rotation, update the best cost for every index and compute the total cost as sum(best) + k * x. This works because additional rotations only introduce new candidate costs for each chocolate. The approach relies on simple iteration and index wrapping, making it a straightforward use of array manipulation and enumeration.
Approach 2: Greedy Approach with Dynamic Programming (O(n^2) time, O(n) space)
Instead of recomputing costs from scratch after each rotation, maintain a running minimum cost for each chocolate type. Think of dp[i] as the cheapest cost discovered so far for type i. For every additional rotation k, update dp[i] = min(dp[i], nums[(i + k) % n]). This greedy update ensures you always keep the lowest available price while rotations reveal new candidates. After updating the array, compute the total cost with the rotation fee. The dynamic programming state compresses all previous rotations into a single array, which avoids redundant work and keeps the logic clean. This approach combines greedy updates with dynamic programming style state tracking.
Recommended for interviews: The greedy + DP simulation is what most interviewers expect. Start by explaining the brute idea of checking all rotations, then show how maintaining a running minimum per chocolate avoids recomputation. That demonstrates both correctness and optimization thinking while keeping the implementation simple.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Operations and Calculate Costs | O(n^2) | O(n) | Clear baseline solution when explaining the effect of rotations and verifying correctness. |
| Greedy with Dynamic Programming | O(n^2) | O(n) | Preferred interview solution. Maintains running minimum costs and avoids recomputation. |