LeetCode 135 Candy - Example and Complexity Analysis

Trace ratings = [1,2,87,87,87,2,1].

Initialize all candies to 1: [1,1,1,1,1,1,1].

Left-to-right:

• 2>1: candy[1]=2. 87>2: candy[2]=3. 87=87: stay. 87=87: stay. 2<87: stay. 1<2: stay.
• After: [1,2,3,1,1,1,1].

Right-to-left:

• 2>1: candy[5]=2. 87>2: candy[4]=3. 87=87: stay. 87>2: candy[2]=max(3,2)=3. 2>1: candy[1]=max(2,2)=2.
• After: [1,2,3,1,3,2,1].

Total: $1+2+3+1+3+2+1 = 13$.

$O(n)$ time, $O(n)$ space.