candy

Published: Jun 21, 2024

Hard Array Greedy

Problem Description

There are n children 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.

Constraints:

  • n == ratings.length
  • 1 <= n <= 2 * 10**4
  • 0 <= ratings[i] <= 2 * 10**4

https://leetcode.com/problems/candy/

Examples

Example 1
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2
Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

How to Solve

This problem asks to create an array with mountains. The common solution of this kind is a two-path enumeration. Firstly, process an array value from left to right. Then, process the array from right to left. Both, if the previous index’s rating is lower than current, the number of candies at the current index should be greater than previous candies by one. Once the two-path enumeration finishes, count total number of candies.

Solution

#include <iostream>
#include <vector>

using namespace std;

class Candy {
public:
    int candy(vector<int>& ratings) {
        ios_base::sync_with_stdio(false);
        cin.tie(0); cout.tie(0);
        
        int n = ratings.size();
        vector<int> candies(n, 1);
        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                candies[i] = candies[i + 1] + 1;
            }
        }
        return reduce(candies.begin(), candies.end());
    }
};







# @param {Integer[]} ratings
# @return {Integer}
def candy(ratings)
    n = ratings.size
    candies = Array.new(n, 1)
    (1...n).each do |idx|
        if ratings[idx] > ratings[idx - 1]
            candies[idx] = candies[idx - 1] + 1
        end
    end
    (n - 2).downto(0) do |idx|
        if ratings[idx] > ratings[idx + 1] && candies[idx] <= candies[idx + 1]
            candies[idx] = candies[idx + 1] + 1
        end
    end
    candies.sum
end

Complexities

  • Time: O(n)
  • Space: O(1)