Greedy Algorithms - Candy Distribution
Given the following code snippet implementing the optimal candy distribution algorithm, what is the final returned value when input ratings = [1, 0, 2]?
Given the following code snippet implementing the optimal candy distribution algorithm, what is the final returned value when input ratings = [1, 0, 2]?
easy🧾 Code Trace Q12 of Q15
Step-by-Step Solution
Step 1: Trace left-to-right pass
ratings = [1,0,2], candies init = [1,1,1] - i=1: ratings[1]=0 < ratings[0]=1, no change - i=2: ratings[2]=2 > ratings[1]=0, candies[2] = candies[1]+1 = 2 candies after pass: [1,1,2]Step 2: Trace right-to-left pass
i=1: ratings[1]=0 < ratings[2]=2, no change i=0: ratings[0]=1 > ratings[1]=0 and candies[0]=1 <= candies[1]=1, update candies[0] = candies[1]+1 = 2 candies after pass: [2,1,2] Sum = 2+1+2 = 5Final Answer:
Option B -> Option BQuick Check:
Sum matches expected output 5 [OK]
Quick Trick: Sum candies after two passes for final answer [OK]
Common Mistakes:
MISTAKES- Forgetting to update candies in right-to-left pass
- Off-by-one errors in loops
- Misreading comparison operators
Trap Explanation:
PITFALL- Candidates often miss the right-to-left pass update, leading to wrong sums.
Interviewer Note:
CONTEXT- Tests ability to mentally execute two-pass greedy code correctly.
Master "Candy Distribution" in Greedy Algorithms
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Greedy Algorithms Quizzes