Collecting Chocolates - Solution & Explanation
Problem Statement
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:
- Simultaneously change the chocolate of
ithtype to((i + 1) mod n)thtype 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 <= 109
Approach Overview
Problem 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 1: Simulate Operations and Calculate Costs
This approach involves simulating the rotations to figure out at which rotation the total cost will be minimal. For each possible initial position, we calculate the cost when collecting chocolates while applying the operation multiple times. We loop up to n times because the chocolates return to their original configuration after n operations.
The solution iterates through each possible rotation. For each rotation, it calculates the cumulative cost, which includes the cost of performing the rotation and the cost of collecting chocolates at each position. It retains the minimum cost encountered during these iterations.
Complexity
Time Complexity: O(n2) — We iterate through each possible rotation and within each rotation, calculate the cost for each chocolate position. Space Complexity: O(1) — We use only a fixed amount of additional space.
Approach 2: Greedy Approach with Dynamic Programming
This approach combines greedy methods with dynamic programming to handle the optimization process efficiently. It builds an understanding of the operations such that unnecessary cycles are avoided by dynamically storing previously calculated minimum operations and reusing them strategically to reduce computation.
The C implementation uses an array to store the minimal costs of chocolates already calculated. This dynamic programming step ensures that each subsequent calculation can build on previous results, leading to efficient reuse of previously computed cycles.
Complexity
Time Complexity: O(n2) — Iterates over potential start points and chocolate types. However, reduced by use of dynamic storage. Space Complexity: O(n) — Stored calculations for each chocolate type.
Approach 3: Enumeration
We consider enumerating the number of operations, and define f[i][j] as the minimum cost after the i-th chocolate has undergone j operations.
For the i-th chocolate:
- If
j = 0, i.e., no operation is performed, thenf[i][j] = nums[i]. - If
0 < j leq n-1, its minimum cost is the minimum cost within the index range[i,.. (i - j + n) bmod n], i.e.,f[i][j] = min{nums[i], nums[i - 1], cdots, nums[(i - j + n) bmod n]}, or it can be written asf[i][j] = min{f[i][j - 1], nums[(i - j + n) bmod n]}. - If
j \ge n, since whenj = n - 1, all minimum costs have been covered, ifjcontinues to increase, the minimum cost will not change, but the increase in the number of operations will lead to an increase in the final cost, so we do not need to consider the case wherej \ge n.
In summary, we can get the state transition equation:
$
f[i][j] =
\begin{cases}
nums[i] ,& j = 0 \
min(f[i][j - 1], nums[(i - j + n) bmod n]) ,& 0 \lt j leq n - 1
\end{cases}
Finally, we only need to enumerate the number of operations j, calculate the minimum cost under each number of operations, and take the minimum value. That is, the answer is min\limits_{0 leq j leq n - 1} sum\limits_{i = 0}^{n - 1} f[i][j] + x times j.
The time complexity is O(n^2), and the space complexity is O(n^2). Where n is the length of the array nums$.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Simulate Operations and Calculate Costs | Time Complexity: O(n2) — We iterate through each possible rotation and within each rotation, calculate the cost for each chocolate position. Space Complexity: O(1) — We use only a fixed amount of additional space. |
| Greedy Approach with Dynamic Programming | Time Complexity: O(n2) — Iterates over potential start points and chocolate types. However, reduced by use of dynamic storage. Space Complexity: O(n) — Stored calculations for each chocolate type. |
| Enumeration | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Leetcode Weekly contest 349 - Medium - Collecting Chocolates • Prakhar Agrawal • 2,189 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Collecting Chocolates easy or hard?
How to solve Collecting Chocolates in O(n)?
What is the best approach for Collecting Chocolates?
What data structure is used in Collecting Chocolates?
What is the time complexity of Collecting Chocolates?
Collecting Chocolates Python or Java solution approach?
Is Collecting Chocolates asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Collecting Chocolates with our built-in code editor and test cases.
Practice on FleetCode