Daily bit(e) of C++ | Candy for greedy children
Daily bit(e) of C++ #135, Common interview problem: Candy for greedy children.
Today we will look at a common C++ interview problem: Candy for greedy children.
Given a line of children with different levels of greediness (represented by an array of integers), determine the minimum number of candies you need to use to satisfy every child.
Each child must receive at least one candy, and each child must receive more candy than their less greedy neighbours.
For example, for the input {1,3,5,2,99,99,1}, the minimum number of candies is 12.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/cc5369doa.
Solution
Let’s consider how we would give out the candy if we only cared about one direction. We would give a child one piece of candy if they are not greedier than their single neighbour and neighbour+1 pieces of candy if they are greedier.
Fortunately, this directly translates to a solution. If we calculate the single-direction values for both directions, the final value for each child is simply max(left,right).
However, we can calculate the number of candies in a single pass. Consider the shapes we are forming with our solution. The most greedy child will be the tip of a peak, which has a left slope, consisting of 1,2,3…l and similarly, a right slope, consisting of 1,2,3…r. Suppose we, therefore, count the consecutive increasing and decreasing steps. In that case, we can calculate the number of candies as l*(l+1)/2 + r*(r+1)/2, with the peak connecting to the taller slope, adding max(l,r)+1 candy.
