Candy Giveaway — a sweet code challenge!

Once in a while, I like to solve code challenges just for the heck of it. Especially when I’m learning a new programming language — it’s a great way to learn!

A few weeks ago, our backend circle at Tikal decided to start learning Rust and last week I ran into the following code-challenge. I thought it was interesting and worth sharing the thought process that took to solve it.

So let’s begin with the problem description

N children are standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [2,0,3]
Output: 5
Explanation: The minimum number of candies we should give would be [2,1,2] candies respectively

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: The minimum number of candies we should give would be [2,2,1] candies respectively

Now that we have seen the problem, how do we approach it?

I always like to start by taking a more complicated example, say: [3,2,1,2,3] or [1,2,3,2,1]

A naive approach will probably try to iterate the list and update a candy-array respectively. But if we try it — we’ll fail, let’s see why:

Rating array: [3,2,1,2,3]

The Candy array is initialized to: [1,1,1,1,1] (because each kid should get at least one candy. Iterating from left to right we see that 3 > 2 so we update the candy array to: [2,1,1,1,1] and if we keep iterating and comparing each element at index i to the element at index i+1 we’ll get [2,2,1,1,1].At this point, we may consider updating both corresponding elements of i and i+1 upon every comparison but it will not work as well because when we have a series of decreasing elements we should bubble back the change, and doing so may be feasible but it’s much more complicated.

Running another iteration will produce [3,2,1,1,1] which is also not good enough. The reason for that is that it’s “not scalable”: say that our ratings array looked like [4,3,2,1] — we would need another iteration in order to get to the solution, and if it was: [5,4,3,2,1] well, you get the idea...

To solve an “increasing elements” problem we should always look back while iterating, meaning: we should compare the element at i+1 to the element at i and if it’s bigger, assign it whatever value we have at candy[i]+1.

If we work with this approach we’ll get the following updates with only a single iteration (one pass — left to right):

i = 0: [1,1,1,1,1]
i = 1: [1,1,1,1,1]
i = 2: [1,1,1,2,1]
i = 3: [1,1,1,2,3]

Now that looks more promising!

We’ll try doing the same thing in the other direction: right to left, comparing i with i-1and we’ll get:

i = 4: [1,1,1,2,3]
i = 3: [1,1,1,2,3]
i = 2: [1,2,1,2,3]
i = 1: [3,2,1,2,3]

Looks like we cracked it, but before we open the champagne let’s take another example and try this approach for [1,2,3,2,1]: doing the “left-to-right” pass will produce:

i = 0: [1,2,1,1,1]
i = 1: [1,2,3,1,1]
i = 2: [1,2,3,1,1]
i = 3: [1,2,3,1,1]

and right-to-left pass: the first step will solve it and the next step will keep the Candy array “as is”:

i = 4: [1,2,3,2,1]
i = 3: [1,2,3,2,1]
i = 2: [1,2,3,2,1]
i = 1: [1,2,3,2,1]

At this point, it looks like the correct solution but we should always try to come up with a few small examples that we consider as edge cases and test our theory, just in case we’re missing something.

Then we will implement this solution in Rust and Typescript just for fun.

use std::cmp;
   
pub fn candy(ratings: Vec<i32>) -> i32 {
    let n = ratings.len();
    if n == 1 {
        return 1;
    }
    let mut res = vec![1; n];
    // first pass - left to right
    for i in 0..=n-2 {
        if ratings[i+1] > ratings[i] {
            res[i+1] = res[i] + 1;
        }            
    }
    // second pass - right to left
    for i in (1..=n-1).rev() {
        if ratings[i-1] > ratings[i] {
            res[i-1] = cmp::max(res[i-1], res[i] + 1);
        }            
    }
    let sum: i32 = res.iter().sum();
    sum
}

function candy(ratings: number[]): number {
    const res = ratings.map(x => 1);
    // first pass (left to right)
    for (let i = 1; i < ratings.length; i++) {
        if (ratings[i] > ratings[i-1]) res[i] = res[i-1]+1;
    }

    // 2nd pass (right to left)
    for (let i = ratings.length-1; i >= 0; i--) {
        if (ratings[i] > ratings[i+1]) res[i] = Math.max(res[i], res[i+1]+1);
    }
    return res.reduce((a,b) => a+b, 0);
}

That’s it for today, I hope you enjoyed it!

Your thoughts/ideas are most welcomed 🙏