Greedy: Distribute Candy

Problem Statement:

There are N children and each child is assigned a rating.

You need to give candies to these children while making sure that each child should get one candy and child with higher rating should get more candies than their neighbors

Example

Input: [1, 2, 2]
Output: 4

You can distribute as [1, 2, 1]

Solution

We need to use greedy method to solve this problem.

We need to traverse the array 2 times.

First from left to right. To check if the child[i] is having a higher rating than child[i-1]. If so, then child[i] will have more candy than the child[i-1].

First from right to left. To check if the child[i] is having a higher rating than child[i+1]. If so, then child[i] will have more candy than the child[i+1].

Then we take the max value of each index of the 2 arrays.
It will give us minimum number of candies required.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

int get_min_candy(int ratings[], int size) 
{
    int sum = 0;
    int left_to_right[10] = {[0 ... 9] = 1};
    int right_to_left[10]  = {[0 ... 9] = 1};

    for (int i = 1 ; i <= size; i++) {
        if (ratings[i] > ratings[i - 1]) {
            left_to_right[i] = left_to_right[i - 1] + 1;
        }
    }

    for (int i = size - 2 ; i >= 0 ; i--) {
        if (ratings[i] > ratings[i + 1]) {
            right_to_left[i] = right_to_left[i + 1] + 1;
        }
    }

    for (int i = 0 ; i < size; i++) {
        sum += max(left_to_right[i], right_to_left[i]);
     }
    return sum;
}
 
int main()
{
    int rating[] = {1, 2, 2};
    int size = 3;
    cout << "The min candy required are " <<get_min_candy(rating, size)
         << endl;
    return 0;
}

Output:

The min candy required are 4