Collecting Chocolates
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process by checking every possible number of rotations. For each number of rotations k (from 0 to n-1), we calculate the total cost. This cost is the sum of two components: the fixed cost for performing k rotations (k * x) and the minimum cost to acquire each of the n types of chocolate, given that we can perform up to k rotations.
Algorithm
- Initialize a variable
minTotalCostto a very large value to store the minimum cost found. - Iterate through all possible numbers of rotations,
k, from0ton-1. - For each
k, calculate the cost associated with this choice: a. Start with the rotation cost, which is(long)k * x. b. For each chocolate typeifrom0ton-1, find its minimum possible acquisition cost. This involves checking its cost at0, 1, ..., krotations. c. The cost of typeiafterjrotations isnums[(i - j + n) % n]. Find the minimum of these values forjin[0, k]. d. Add this minimum cost for typeito a running sum for the currentk. - After summing the minimum costs for all types, add the rotation cost
k * xto get the total cost forkrotations. - Update
minTotalCost = min(minTotalCost, currentTotalCost). - After checking all
kfrom0ton-1,minTotalCostwill hold the answer.
Walkthrough
The fundamental idea is to exhaustively check all scenarios. A scenario is defined by the total number of rotation operations we decide to perform. Let's say we decide to perform k rotations. The cost for these operations is k * x. Once we've paid this price, we can collect each chocolate type i. For each type i, we have the choice to collect it after 0 rotations (cost nums[i]), 1 rotation (cost nums[(i-1+n)%n]), ..., or k rotations (cost nums[(i-k+n)%n]). Naturally, we'd pick the cheapest option available up to k rotations. We calculate this minimum cost for each of the n types, sum them up, and add the initial k * x rotation cost. By doing this for every possible k from 0 to n-1 and taking the minimum of all total costs, we find the global minimum cost.
class Solution { public long minCost(int[] nums, int x) { int n = nums.length; long minTotalCost = Long.MAX_VALUE; // k is the number of rotations for (int k = 0; k < n; k++) { long currentRotationCost = (long) k * x; long currentChocolatesCost = 0; // i is the type of chocolate for (int i = 0; i < n; i++) { long minCostForTypeI = (long) nums[i]; // j is the number of rotations when we buy chocolate i for (int j = 1; j <= k; j++) { minCostForTypeI = Math.min(minCostForTypeI, (long) nums[(i - j + n) % n]); } currentChocolatesCost += minCostForTypeI; } long currentTotalCost = currentRotationCost + currentChocolatesCost; minTotalCost = Math.min(minTotalCost, currentTotalCost); } return minTotalCost; }}Complexity
Time
O(n^3). There are three nested loops. The outer loop for `k` runs `n` times. The second loop for `i` runs `n` times. The innermost loop for `j` runs up to `n` times. This results in a cubic time complexity.
Space
O(1) extra space. We only use a few variables to keep track of costs, independent of the input size `n`.
Trade-offs
Pros
It is a straightforward implementation of the problem statement.
It requires no extra space apart from a few variables for calculation.
Cons
The
O(n^3)time complexity makes it too slow for the given constraints, likely resulting in a 'Time Limit Exceeded' error on larger test cases.
This approach improves upon the brute-force method by using a dynamic programming-like optimization. Instead of re-calculating the minimum cost for each chocolate type from scratch for every number of rotations, we maintain an array of the minimum costs found so far. As we consider an additional rotation (k), we can efficiently update these minimum costs by just comparing them with the new costs available after this k-th rotation.
Algorithm
- Initialize an array
minCostsSoFarof sizenwith the initial costs fromnums. This represents the minimum costs fork=0rotations. - Calculate the initial total cost by summing up
minCostsSoFarand store it inminTotalCost. - Iterate
kfrom1ton-1, representing the number of rotations. - In each iteration
k: a. Calculate the rotation cost:rotationCost = (long)k * x. b. InitializecurrentChocolatesCost = 0. c. Iterate through each chocolate typeifrom0ton-1: i. The cost of typeiafterkrotations isnums[(i - k + n) % n]. ii. Update the minimum cost for typei:minCostsSoFar[i] = min(minCostsSoFar[i], new_cost). iii. Add the updatedminCostsSoFar[i]tocurrentChocolatesCost. d. Calculate the total cost forkrotations:totalCostForK = rotationCost + currentChocolatesCost. e. Update the overall minimum:minTotalCost = min(minTotalCost, totalCostForK). - Return
minTotalCost.
Walkthrough
We can observe that the calculation in the brute-force approach is highly redundant. The minimum cost for a type i with k rotations is simply the minimum of its cost with k-1 rotations and its cost at exactly k rotations. This suggests an iterative solution.
We can iterate through the number of rotations k from 0 to n-1. We'll use an auxiliary array, minCostsSoFar, of size n, where minCostsSoFar[i] stores the minimum cost to acquire chocolate of type i considering all rotations from 0 up to the current k.
- For
k=0,minCostsSoFaris just a copy of thenumsarray. The total cost is the sum of these costs. - For
k=1, we update eachminCostsSoFar[i]by comparing its current value with the cost of typeiafter 1 rotation, which isnums[(i-1+n)%n]. We then compute the new total cost:(1 * x) + sum(minCostsSoFar). - We continue this process for
kup ton-1. In each stepk, we updateminCostsSoFar[i]withmin(minCostsSoFar[i], nums[(i-k+n)%n])and recalculate the total cost. The overall minimum of these total costs is the answer.
This avoids the innermost loop of the brute-force approach, reducing the complexity from cubic to quadratic.
class Solution { public long minCost(int[] nums, int x) { int n = nums.length; // minCostsSoFar[i] stores the minimum cost to collect chocolate of type i // considering all rotations from 0 up to the current k. long[] minCostsSoFar = new long[n]; for (int i = 0; i < n; i++) { minCostsSoFar[i] = nums[i]; } long minTotalCost = 0; for (long cost : minCostsSoFar) { minTotalCost += cost; } // k is the number of rotations for (int k = 1; k < n; k++) { long currentChocolatesCost = 0; // i is the type of chocolate for (int i = 0; i < n; i++) { // Cost of type 'i' after 'k' rotations is nums[(i - k + n) % n] long costAfterKRotations = (long) nums[(i - k + n) % n]; minCostsSoFar[i] = Math.min(minCostsSoFar[i], costAfterKRotations); currentChocolatesCost += minCostsSoFar[i]; } long currentTotalCost = (long) k * x + currentChocolatesCost; minTotalCost = Math.min(minTotalCost, currentTotalCost); } return minTotalCost; }}Complexity
Time
O(n^2). The outer loop for `k` runs `n` times. The inner loop to update and sum costs also runs `n` times. This results in a quadratic time complexity.
Space
O(n). We use an auxiliary array `minCostsSoFar` of size `n` to store the running minimum costs for each chocolate type.
Trade-offs
Pros
Significantly more efficient than the brute-force approach with
O(n^2)complexity.Optimal for the given constraints and passes all test cases.
Cons
Requires O(n) extra space to store the minimum costs for each chocolate type.
Solutions
Solution
class Solution {public long minCost(int[] nums, int x) { int n = nums.length; int[][] f = new int[n][n]; for (int i = 0; i < n; ++i) { f[i][0] = nums[i]; for (int j = 1; j < n; ++j) { f[i][j] = Math.min(f[i][j - 1], nums[(i - j + n) % n]); } } long ans = 1L << 60; for (int j = 0; j < n; ++j) { long cost = 1L * x * j; for (int i = 0; i < n; ++i) { cost += f[i][j]; } ans = Math.min(ans, cost); } return ans; }}class Solution: def minCost(self, nums: List[int], x: int) -> int: n = len(nums) f = [[0] * n for _ in range(n)] for i, v in enumerate(nums): f[i][0] = v for j in range(1, n): f[i][j] = min(f[i][j - 1], nums[(i - j) % n]) return min(sum(f[i][j] for i in range(n)) + x * j for j in range(n))class Solution {public: long long minCost(vector<int> &nums, int x) { int n = nums.size(); int f[n][n]; for (int i = 0; i < n; ++i) { f[i][0] = nums[i]; for (int j = 1; j < n; ++j) { f[i][j] = min(f[i][j - 1], nums[(i - j + n) % n]); } } long long ans = 1LL << 60; for (int j = 0; j < n; ++j) { long long cost = 1LL * x * j; for (int i = 0; i < n; ++i) { cost += f[i][j]; } ans = min(ans, cost); } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.