Collecting Chocolates — LeetCode 2735 Python Solution
MediumArrayEnumeration
- Problem
- #2735
- Reading time
- 2 min
- Source
- leetcode.com
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].
Example
- 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.
Python solution
Python
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))Complexity
| Measure | Complexity |
|---|---|
| Time | O(n^2) |
| Space | O(n^2) auxiliary |
Related problems
LeetCode 1534Count Good TripletsEasyLeetCode 1566Detect Pattern of Length M Repeated K or More TimesEasyLeetCode 1620Coordinate With Maximum Network QualityMediumLeetCode 2765Longest Alternating SubarrayEasyLeetCode 2778Sum of Squares of Special ElementsEasyLeetCode 2934Minimum Operations to Maximize Last Elements in ArraysMedium
Frequently asked questions
- How hard is LeetCode 2735. Collecting Chocolates?
- LeetCode 2735. Collecting Chocolates is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2735. Collecting Chocolates?
- The Python solution on this page runs in O(n^2).
- What is the space complexity of LeetCode 2735. Collecting Chocolates?
- The Python solution on this page uses O(n^2) auxiliary space.
- What topics does LeetCode 2735. Collecting Chocolates cover?
- LeetCode 2735. Collecting Chocolates is tagged Array and Enumeration on LeetCode.