DAY 9 - Candy Distribution Problem

Hey. You are reading day-9 of the 100 Days Challenge. This is Nayan Pahuja.
Today we are going to solve another problem that are solved using greedy algorithms.

Let's get right on to it.
PS:- While I am writing this article, Leetcode seems to be under maintenance for the moment. I will update the code of this question back when I get a chance.

DAY 9 Problem 1: Candy Distribution Problem

The problem states that distribute the minimum number of candies to N children such that:

• Each child must have at least one candy.
• The children with a higher ranking will get more candies than their neighbors.

Note that each child has a rating. The task is to the minimum number of candies you must give.

Intuition:

The problem is rather easy for being a leetcode hard problem. There is not much to sweat. Let's note down our observation and clear a misconception first.

All Children have must 1 candy.
All children must be compared with both of it's neighbors before updating it's candies.
It must have a higher rating than both of it's neighbors not equal to but higher.

Approach:

• We will solve this by passing the ratings array 2 times.

• One from left to right and another traversing back from right to left.

• We will first initialize a vector of integer having value 1. This array will be used to store the candies of each child per their rating.

• Then we will traverse through ratings from left to right incrementing the count of that index's child's candies greater than it's successor's if it satisfies the conditions.

• Then while returning back from right to left. We will check the same condition for its left neighbors but will also check if it already satisfies the conditions of being greater than it's neighbors.

• If it satisfies these conditions, we shall increment it by 1 else we shall not.

Code:

int candy(vector<int>& ratings) {
        //extreme cases
        if(ratings.size() == 1)
        {
            return 1;
        }
        int n = ratings.size();
        vector<int> totalCandies(n,1);
        for(int i = 1; i < n; i++)
        {
            if(ratings[i] > ratings[i-1])
            {
                totalCandies[i] = totalCandies[i-1]+1;
            }
        }
        for(int i = n-2; i > -1 ; i--)
        {
            if(ratings[i] > ratings[i+1] && totalCandies[i] <= totalCandies[i+1])
            {
                totalCandies[i] = totalCandies[i+1]+1;
            }
        }
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            sum = sum + totalCandies[i];
        }

        return sum;

    }

Complexity Analysis

Time Complexity: O(N) + O(N) ~= O(N).
Space Complexity: O(N)