Greedy Algorithms - Candy Distribution
Given the final candies array [2, 1, 2] after running the optimal candy distribution algorithm, which of the following could be the original ratings array?
Given the final candies array [2, 1, 2] after running the optimal candy distribution algorithm, which of the following could be the original ratings array?
hard🔄 Reverse Engineer Q9 of Q15
Step-by-Step Solution
Solution:
Step 1: Analyze candies and constraints
Candies: [2,1,2] imply middle child has lowest rating, neighbors higher.Step 2: Match ratings pattern
Ratings [1,0,2] fit: 1 > 0, 2 > 0, consistent with candies.Step 3: Exclude others
[1,2,3] would have increasing candies; [2,2,2] equal candies; [3,2,1] decreasing candies.Final Answer:
Option B -> Option BQuick Check:
Candies match ratings with valley at middle child [OK]
Quick Trick: Candies reflect local rating comparisons; identify valleys and peaks [OK]
Common Mistakes:
MISTAKES- Assuming candies equal ratings
- Ignoring neighbor constraints
- Confusing increasing with decreasing sequences
Trap Explanation:
PITFALL- Candidates often pick ratings that don't match candy distribution constraints.
Interviewer Note:
CONTEXT- Tests deep understanding by reasoning backward from output
Master "Candy Distribution" in Greedy Algorithms
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Greedy Algorithms Quizzes