Candy on the trading floor

Question

Traders sit in a row, each with a performance rating. You give each at least one treat, and any trader rated higher than an immediate neighbor must get strictly more treats than that neighbor. Minimize the total handed out.

ratings = [1, 0, 2]  ->  5      # treats [2, 1, 2]
ratings = [1, 2, 2]  ->  4      # treats [1, 2, 1]

Return the minimum total number of treats.

Accepted Answer

Each trader's requirement comes from two directions, and no single pass sees both. So sweep twice. First left to right: whenever a trader out-rates the neighbor on the left, give one more than that left neighbor. Then right to left: whenever a trader out-rates the right neighbor, bump their count to at least one more than the right neighbor, taking the max so the left-pass guarantee is not lost. Tracing [1, 0, 2]: start [1,1,1]. Left pass: index 2 out-rates index 1, so it becomes 2, giving [1,1,2]. Right pass: index 0 out-rates index 1, so it becomes max(1, 1 + 1) = 2, giving [2,1,2], sum 5. …

Candy on the trading floor

Your answer

More Coding questions