# The two-scanning solution can guarantee the result is optimal? Any proof?

• After reading the two-scanning solution to this question several times, I still cannot make myself sure that the result is optimal. Could anyone give a strict proof to it? Thanks!

• The two scan method is not elegant but it is easy to prove.

Assume after two-scan method, there is one kid has higher rate than his/her neighbor but get less candies, say k.

ratings[k] > rating[k-1] && rating[k] > rating[k+1]

If k gets less candies than k-1, it violates the first pass that if ratings[k] > rating[k-1] then candy[k]=candy[k-1]+1.

If k gets less candies than k+1, it violates the second pass that if ratings[k] > rating[k+1] then candy[k]=max(candy[k], candy[k+1]+1).

Thus, k does not get less candies than both of his neighbors. The assumption does not valid. The solution is proved.

• Use the height of rectangles to represent the number of candies that the kids get. We will get a lot of peaks.
• Every peak is independent. So we can divide the candy distribution into independent peaks.
• We can prove that the construction of a single peak is optimal, we can prove the whole candy distribution is optimal.
• It’s easy to prove every single peak is optimal.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.