Question

Formatted question description: https://leetcode.ca/all/135.html

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.

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.

Constraints:

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

Algorithm

To begin with, we initialize one candy for each person, and then traverse the array twice:

First, traverse from left to right. If the rating of the current student is higher than the previous student, we add one more candy to ensure more candies are given in the left-to-right direction.
Next, traverse from right to left. If the rating of the current student is higher than the next student and they have fewer candies than the next student, we give the current student one more candy than the next student.

Finally, we add up the number of candies for all students.

Here are four test cases using the ratings array:

Monotonically increasing: [7, 8, 9]
Monotonically decreasing: [9, 8, 7]
Wave shape: [7, 8, 9, 8, 7]
Wave trough shape: [9, 8, 7, 8, 9]

Code

public class Candy {

	public class Solution {
	    public int candy(int[] ratings) {

	        int sum = 0;

	        if (ratings == null || ratings.length == 0) {
	            return sum;
	        }

	        int[] candies = new int[ratings.length];

	        // scan from left, and then scan from right
	        for (int i = 1; i < ratings.length; i++) {
	        	// start from 2nd element

	        	if (ratings[i] > ratings[i - 1]) {
	        		candies[i] = candies[i] < candies[i - 1] + 1 ? candies[i - 1] + 1 : candies[i];

	        	}
	        }

	        for (int i = ratings.length - 2; i >= 0; i--) {
	        	// also, start from 2nd last

	        	if (ratings[i] > ratings[i + 1]) {
	        		candies[i] = candies[i] < candies[i + 1] + 1 ? candies[i + 1] + 1 : candies[i];
	        	}
	        }

	        for (int each: candies) {
	        	sum += each;
	        }

	        return sum + ratings.length; // at least one candy for each
	    }
	}

}

############

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.max(left[i], right[i]);
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/candy/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int candy(vector<int>& A) {
        int N = A.size();
        vector<int> v(N);
        queue<int> q;
        for (int i = 0; i < N; ++i) {
            if ((i - 1 < 0 || A[i] <= A[i - 1]) && (i + 1 >= N || A[i] <= A[i + 1])) {
                q.push(i);
                v[i] = 1;
            }
        }
        while (q.size()) {
            int i = q.front();
            q.pop();
            for (int j = -1; j <= 1; j += 2) {
                int k = i + j;
                if (k < 0 || k >= N) continue;
                if (A[k] > A[i] && v[k] < 1 + v[i]) {
                    v[k] = 1 + v[i];
                    q.push(k);
                }
            }
        }
        return accumulate(begin(v), end(v), 0);
    }
};

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        left = [1] * n
        right = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right[i] = right[i + 1] + 1
        return sum(max(a, b) for a, b in zip(left, right))

############

class Solution(object):
  def candy(self, ratings):
    """
    :type ratings: List[int]
    :rtype: int
    """
    n = len(ratings)
    left = [1] * n
    ans = 0
    for i in range(1, n):
      if ratings[i] > ratings[i - 1]:
        left[i] = left[i - 1] + 1
    ans = left[-1]
    for i in reversed(range(0, n - 1)):
      if ratings[i] > ratings[i + 1]:
        left[i] = max(left[i], left[i + 1] + 1)
      ans += left[i]
    return ans

func candy(ratings []int) int {
	n := len(ratings)
	left := make([]int, n)
	right := make([]int, n)
	for i := range left {
		left[i] = 1
		right[i] = 1
	}
	for i := 1; i < n; i++ {
		if ratings[i] > ratings[i-1] {
			left[i] = left[i-1] + 1
		}
	}
	for i := n - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] {
			right[i] = right[i+1] + 1
		}
	}
	ans := 0
	for i, a := range left {
		b := right[i]
		ans += max(a, b)
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

function candy(ratings: number[]): number {
    const n = ratings.length;
    const left = new Array(n).fill(1);
    const right = new Array(n).fill(1);
    for (let i = 1; i < n; ++i) {
        if (ratings[i] > ratings[i - 1]) {
            left[i] = left[i - 1] + 1;
        }
    }
    for (let i = n - 2; i >= 0; --i) {
        if (ratings[i] > ratings[i + 1]) {
            right[i] = right[i + 1] + 1;
        }
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        ans += Math.max(left[i], right[i]);
    }
    return ans;
}

public class Solution {
    public int Candy(int[] ratings) {
        int n = ratings.Length;
        int[] candies = new int[n];
        Array.Fill(candies, 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] = Math.Max(candies[i], candies[i + 1] + 1);
            }
        }
        return candies.Sum();
    }
}

135 - Candy

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions