NeetCode #278LC-2226MediumBinary Search
← Back to All Problems#278 · #2226 · Maximum Candies Allocated to K Children(分配给 K 个孩子的最大糖果数)
📌 Problem Statement & Constraints
You are given a 0-indexed integer array
candies where candies[i] is the number of candies in the i-th pile, and an integer k. Each child receives candies from a single pile, and piles cannot be split across children. Return the maximum number of candies each child can get. Constraints: 1 <= candies.length <= 10^5, 1 <= candies[i] <= 10^7, 1 <= k <= 10^12.💡 Core Algorithmic Approaches
- Binary search on the answer: "can each of the
kchildren get at leastccandies" is monotone inc. - For a given
c, the number of children that can be served issum(pile // c). - The answer is feasible when that count is at least
k. Use the upper-biased midpoint to maximise. - If the total number of candies is less than
k, the answer is 0 -- check this before the search.
💻 Benchmark Python3 Implementation
class Solution:
def maximumCandies(self, candies: List[int], k: int) -> int:
if sum(candies) < k:
return 0 # impossible to give everyone one
lo, hi = 1, max(candies)
while lo < hi:
mid = (lo + hi + 1) // 2 # upper-biased: maximise
children = sum(c // mid for c in candies)
if children >= k:
lo = mid # feasible -> try larger
else:
hi = mid - 1
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log(max(candies))): each predicate is O(n).
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Using the lower-biased midpoint with
lo = mid: infinite loop; the upper bias is required for maximisation. - Forgetting the feasibility check: if the total is less than
k, the binary search would still return 1 (sincemid = 1always givessum(candies) >= k... which is false), so the guard is needed. - Allowing a pile to be split between children: each child takes from exactly one pile, which is why the floor division is used.
- Using
children == kinstead of>= k: serving more children than required is fine; the surplus is simply unused.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.