2735. Collecting Chocolates Solution & Code

Q: Is Collecting Chocolates easy or hard?

Collecting Chocolates is rated Medium difficulty on LeetCode. The challenge comes from recognizing that rotations reveal new candidate costs and that maintaining a running minimum per index avoids recomputing values from scratch.

Q: How to solve Collecting Chocolates in O(n)?

A strict O(n) solution is not known for the general constraints. Each rotation potentially introduces a new candidate cost for every chocolate type, which requires scanning the array. Most accepted implementations run in O(n^2) time with O(n) space using incremental minimum tracking.

Q: What is the best approach for Collecting Chocolates?

The greedy approach with dynamic programming is the most practical solution. Maintain a running minimum cost for each chocolate type while iterating through all possible rotations. For each rotation k, update the minimum cost and add the rotation fee k * x. This results in O(n^2) time and O(n) space.

Q: What data structure is used in Collecting Chocolates?

The solution primarily uses arrays. A secondary array (or DP array) stores the minimum cost found so far for each chocolate type as rotations are simulated.

Q: What is the time complexity of Collecting Chocolates?

The standard solution runs in O(n^2) time because the algorithm evaluates up to n rotations and updates n chocolate costs during each rotation. Space complexity is O(n) for storing the minimum cost for each chocolate type.

Q: Collecting Chocolates Python or Java solution approach?

Both Python and Java implementations typically simulate rotations while maintaining a minimum-cost array. For every rotation k, update dp[i] = min(dp[i], nums[(i + k) % n]) and compute the total cost including the rotation fee. The logic remains identical across languages.

Q: Is Collecting Chocolates asked at Google, Amazon, or Meta?

This problem follows patterns commonly used in interviews at companies like Amazon and Google, especially questions involving array rotation, cost minimization, and dynamic updates. It tests reasoning about cyclic arrays and incremental optimization.

The problem

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 i^th type.

In one operation, you can do the following with an incurred cost of x:

Simultaneously change the chocolate of i^th 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 1^st 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 2^ndtype 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 0^thtype 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 <= 1000
1 <= nums[i] <= 10⁹
1 <= x <= 10⁹

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.

Python

def min_cost(nums, x):
    n = len(nums)
    min_cost = float('inf')

    for i in range(n):
        current_cost = i * x
        for j in range(n):
            current_cost += nums[(j - i + n) % n]
        min_cost = min(min_cost, current_cost)

    return min_cost

if __name__ == "__main__":
    nums = [20, 1, 15]
    x = 5
    print(f"Output: {min_cost(nums, x)}")

Java

import java.util.Arrays;

public class ChocolateCollection {
    public static int minCost(int[] nums, int x) {
        int n = nums.length;
        int minCost = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int currentCost = i * x;
            for (int j = 0; j < n; j++) {
                currentCost += nums[(j - i + n) % n];
            }
            minCost = Math.min(minCost, currentCost);
        }
        return minCost;
    }

    public static void main(String[] args) {
        int[] nums = {20, 1, 15};
        int x = 5;
        System.out.println("Output: " + minCost(nums, x));
    }
}

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minCost(vector<int>& nums, int x) {
    int n = nums.size();
    int minCost = INT_MAX;
    
    for (int i = 0; i < n; ++i) {
        int currentCost = i * x;
        for (int j = 0; j < n; ++j) {
            currentCost += nums[(j - i + n) % n];
        }
        minCost = min(minCost, currentCost);
    }
    return minCost;
}

int main() {
    vector<int> nums = {20, 1, 15};
    int x = 5;
    cout << "Output: " << minCost(nums, x) << endl;
    return 0;
}

JavaScript

function minCost(nums, x) {
    const n = nums.length;
    let minCost = Infinity;

    for (let i = 0; i < n; i++) {
        let currentCost = i * x;
        for (let j = 0; j < n; j++) {
            currentCost += nums[(j - i + n) % n];
        }
        minCost = Math.min(minCost, currentCost);
    }
    return minCost;
}

const nums = [20, 1, 15];
const x = 5;
console.log(`Output: ${minCost(nums, x)}`);

#include <stdio.h>
#include <limits.h>

int minCost(int* nums, int numsSize, int x) {
    int totalCost = 0, minCost = INT_MAX;
    for (int i = 0; i < numsSize; ++i) {
        totalCost = i * x; // cost for i rotations
        for (int j = 0; j < numsSize; ++j) {
            totalCost += nums[(j - i + numsSize) % numsSize];
        }
        if (totalCost < minCost) minCost = totalCost;
    }
    return minCost;
}

int main() {
    int nums[] = {20, 1, 15};
    int x = 5;
    int result = minCost(nums, 3, x);
    printf("Output: %d\n", result);
    return 0;
}

using System;

public class ChocolateCollection {
    public static int MinCost(int[] nums, int x) {
        int n = nums.Length;
        int minCost = int.MaxValue;

        for (int i = 0; i < n; i++) {
            int currentCost = i * x;
            for (int j = 0; j < n; j++) {
                currentCost += nums[(j - i + n) % n];
            }
            minCost = Math.Min(minCost, currentCost);
        }
        return minCost;
    }

    public static void Main() {
        int[] nums = {20, 1, 15};
        int x = 5;
        Console.WriteLine("Output: " + MinCost(nums, x));
    }
}

This Python function iterates through each possible initial rotation state, calculating the total collection cost and maintaining a record of the minimal cost found. It uses Python's modulus to simulate the rotational indexing.

Complexity

Time Complexity: O(n²) — Every potential state of chocolate types is evaluated relative to every index. Space Complexity: O(1) — Minimal extra space beyond primitive counters.

Try this approach in the editor

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.

Python

def min_cost(nums, x):
    n = len(nums)
    dp = [float('inf')] * n
    min_cost = float('inf')

    for s in range(n):
        total_cost = 0
        for j in range(n):
            dp_idx = (j - s + n) % n
            dp[dp_idx] = min(dp[dp_idx], nums[j])
            total_cost += dp[dp_idx]
        total_cost += s * x
        min_cost = min(min_cost, total_cost)

    return min_cost

if __name__ == "__main__":
    nums = [20, 1, 15]
    x = 5
    print(f"Output: {min_cost(nums, x)}")

Java

import java.util.Arrays;

public class ChocolateCollection {
    public static int minCost(int[] nums, int x) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        int minCost = Integer.MAX_VALUE;

        for (int s = 0; s < n; ++s) {
            int totalCost = 0;
            for (int j = 0; j < n; ++j) {
                int dpIdx = (j - s + n) % n;
                dp[dpIdx] = Math.min(dp[dpIdx], nums[j]);
                totalCost += dp[dpIdx];
            }
            totalCost += s * x;
            minCost = Math.min(minCost, totalCost);
        }
        return minCost;
    }

    public static void main(String[] args) {
        int[] nums = {20, 1, 15};
        int x = 5;
        System.out.println("Output: " + minCost(nums, x));
    }
}

C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int minCost(vector<int>& nums, int x) {
    vector<int> dp(nums.size(), INT_MAX);
    int n = nums.size();
    int minCost = INT_MAX;

    for (int s = 0; s < n; ++s) {
        int totalCost = 0;
        for (int j = 0; j < n; ++j) {
            int dpIdx = (j - s + n) % n;
            dp[dpIdx] = min(dp[dpIdx], nums[j]);
            totalCost += dp[dpIdx];
        }
        totalCost += s * x;
        minCost = min(minCost, totalCost);
    }
    return minCost;
}

int main() {
    vector<int> nums = {20, 1, 15};
    int x = 5;
    cout << "Output: " << minCost(nums, x) << endl;
    return 0;
}

JavaScript

function minCost(nums, x) {
    const n = nums.length;
    const dp = Array(n).fill(Infinity);
    let minCost = Infinity;

    for (let s = 0; s < n; s++) {
        let totalCost = 0;
        for (let j = 0; j < n; j++) {
            const dpIdx = (j - s + n) % n;
            dp[dpIdx] = Math.min(dp[dpIdx], nums[j]);
            totalCost += dp[dpIdx];
        }
        totalCost += s * x;
        minCost = Math.min(minCost, totalCost);
    }
    return minCost;
}

const nums = [20, 1, 15];
const x = 5;
console.log(`Output: ${minCost(nums, x)}`);

#include <stdio.h>
#include <limits.h>

int minCost(int* nums, int numsSize, int x) {
    int dp[1000], minCost = INT_MAX;

    for (int s = 0; s < numsSize; ++s) { // Start point loop
        int totalCost = 0;
        for (int j = 0; j < numsSize; ++j) {
            int dpIdx = (j - s + numsSize) % numsSize;
            if (j == 0 || dp[dpIdx] > nums[j]) { // Use DP to store minimum
                dp[dpIdx] = nums[j];
            }
            totalCost += dp[dpIdx];
        }
        totalCost += s * x; // Rotation cost
        if (totalCost < minCost) minCost = totalCost;
    }

    return minCost;
}

int main() {
    int nums[] = {20, 1, 15};
    int x = 5;
    int result = minCost(nums, 3, x);
    printf("Output: %d\n", result);
    return 0;
}

using System;

public class ChocolateCollection {
    public static int MinCost(int[] nums, int x) {
        int n = nums.Length;
        int[] dp = new int[n];
        Array.Fill(dp, int.MaxValue);
        int minCost = int.MaxValue;

        for (int s = 0; s < n; ++s) {
            int totalCost = 0;
            for (int j = 0; j < n; ++j) {
                int dpIdx = (j - s + n) % n;
                dp[dpIdx] = Math.Min(dp[dpIdx], nums[j]);
                totalCost += dp[dpIdx];
            }
            totalCost += s * x;
            minCost = Math.Min(minCost, totalCost);
        }
        return minCost;
    }

    public static void Main() {
        int[] nums = {20, 1, 15};
        int x = 5;
        Console.WriteLine("Output: " + MinCost(nums, x));
    }
}

This solution utilizes a dynamic list to track reduced indices while looping over start points. By updating dynamically, it reduces redundant re-calculation, allowing reuse of prior minimized results for subsequent computation.

Complexity

Time Complexity: O(n²) — Number of possible operations reduced through dynamic memorization. Space Complexity: O(n) — Required space for storing previously minimized indices.

Try this approach in the editor

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, then f[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 as f[i][j] = min{f[i][j - 1], nums[(i - j + n) bmod n]}.
If j \ge n, since when j = n - 1, all minimum costs have been covered, if j continues 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 where j \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$.

TypeScript

function minCost(nums: number[], x: number): number {
    const n = nums.length;
    const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = 0; i < n; ++i) {
        f[i][0] = nums[i];
        for (let j = 1; j < n; ++j) {
            f[i][j] = Math.min(f[i][j - 1], nums[(i - j + n) % n]);
        }
    }
    let ans = Infinity;
    for (let j = 0; j < n; ++j) {
        let cost = x * j;
        for (let i = 0; i < n; ++i) {
            cost += f[i][j];
        }
        ans = Math.min(ans, cost);
    }
    return ans;
}

func minCost(nums []int, x int) int64 {
	n := len(nums)
	f := make([][]int, n)
	for i, v := range nums {
		f[i] = make([]int, n)
		f[i][0] = v
		for j := 1; j < n; j++ {
			f[i][j] = min(f[i][j-1], nums[(i-j+n)%n])
		}
	}
	ans := 1 << 60
	for j := 0; j < n; j++ {
		cost := x * j
		for i := 0; i < n; i++ {
			cost += f[i][j]
		}
		ans = min(ans, cost)
	}
	return int64(ans)
}

Rust

impl Solution {
    pub fn min_cost(nums: Vec<i32>, x: i32) -> i64 {
        let n = nums.len();
        let mut f = vec![vec![0; n]; n];
        for i in 0..n {
            f[i][0] = nums[i];
            for j in 1..n {
                f[i][j] = f[i][j - 1].min(nums[(i - j + n) % n]);
            }
        }
        let mut ans = i64::MAX;
        for j in 0..n {
            let mut cost = (x as i64) * (j as i64);
            for i in 0..n {
                cost += f[i][j] as i64;
            }
            ans = ans.min(cost);
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Simulate Operations and Calculate Costs	Time Complexity: O(n²) — Every potential state of chocolate types is evaluated relative to every index. Space Complexity: O(1) — Minimal extra space beyond primitive counters.
Greedy Approach with Dynamic Programming	Time Complexity: O(n²) — Number of possible operations reduced through dynamic memorization. Space Complexity: O(n) — Required space for storing previously minimized indices.
Enumeration	–

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.

Frequently asked questions

Is Collecting Chocolates easy or hard?

Collecting Chocolates is rated Medium difficulty on LeetCode. The challenge comes from recognizing that rotations reveal new candidate costs and that maintaining a running minimum per index avoids recomputing values from scratch.

How to solve Collecting Chocolates in O(n)?

A strict O(n) solution is not known for the general constraints. Each rotation potentially introduces a new candidate cost for every chocolate type, which requires scanning the array. Most accepted implementations run in O(n^2) time with O(n) space using incremental minimum tracking.

What is the best approach for Collecting Chocolates?

The greedy approach with dynamic programming is the most practical solution. Maintain a running minimum cost for each chocolate type while iterating through all possible rotations. For each rotation k, update the minimum cost and add the rotation fee k * x. This results in O(n^2) time and O(n) space.

What data structure is used in Collecting Chocolates?

The solution primarily uses arrays. A secondary array (or DP array) stores the minimum cost found so far for each chocolate type as rotations are simulated.

What is the time complexity of Collecting Chocolates?

The standard solution runs in O(n^2) time because the algorithm evaluates up to n rotations and updates n chocolate costs during each rotation. Space complexity is O(n) for storing the minimum cost for each chocolate type.

Collecting Chocolates Python or Java solution approach?

Both Python and Java implementations typically simulate rotations while maintaining a minimum-cost array. For every rotation k, update dp[i] = min(dp[i], nums[(i + k) % n]) and compute the total cost including the rotation fee. The logic remains identical across languages.

Is Collecting Chocolates asked at Google, Amazon, or Meta?

This problem follows patterns commonly used in interviews at companies like Amazon and Google, especially questions involving array rotation, cost minimization, and dynamic updates. It tests reasoning about cyclic arrays and incremental optimization.

Collecting Chocolates solution and explanation

The problem

Approach overview

Approach 1: Simulate Operations and Calculate Costs

Approach 2: Greedy Approach with Dynamic Programming

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Collecting Chocolates solution and explanation

The problem

Approach overview

Approach 1: Simulate Operations and Calculate Costs

Approach 2: Greedy Approach with Dynamic Programming

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems