Number of Unique Flavors After Sharing K Candies — LeetCode 2107 Python Solution
MediumLeetCode PremiumArrayHash TableSliding Window
- Problem
- #2107
- Pattern
- Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a 0-indexed integer array candies, where candies[i] represents the flavor of the ith candy. Your mom wants you to share these candies with your little sister by giving her k consecutive candies, but you want to keep as many flavors of candies as possible.
Example
- Input
- candies = [1,2,2,3,4,3], k = 3
- Output
- 3
- Explanation
- Give the candies in the range [1, 3] (inclusive) with flavors [2,2,3].
Python solution
Python
class Solution:
def shareCandies(self, candies: List[int], k: int) -> int:
cnt = Counter(candies[k:])
ans = len(cnt)
for i in range(k, len(candies)):
cnt[candies[i - k]] += 1
cnt[candies[i]] -= 1
if cnt[candies[i]] == 0:
cnt.pop(candies[i])
ans = max(ans, len(cnt))
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2107. Number of Unique Flavors After Sharing K Candies is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2107. Number of Unique Flavors After Sharing K Candies?
- LeetCode 2107. Number of Unique Flavors After Sharing K Candies is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2107. Number of Unique Flavors After Sharing K Candies?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2107. Number of Unique Flavors After Sharing K Candies?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2107. Number of Unique Flavors After Sharing K Candies cover?
- LeetCode 2107. Number of Unique Flavors After Sharing K Candies is tagged Array, Hash Table and Sliding Window on LeetCode.
- Is LeetCode 2107. Number of Unique Flavors After Sharing K Candies a premium problem?
- Yes. LeetCode 2107. Number of Unique Flavors After Sharing K Candies is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.