Problem Statement:
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: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
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.length1 <= n <= 2 * 1040 <= ratings[i] <= 2 * 104
Approach:
- Every child must get at least 1 candy → start with
ans = n. - Traverse the ratings array and look for
increasing and decreasing slopes.- Increasing slope (up): When
arr[i] > arr[i-1], keep incrementing up. Add candies accordingly. - Decreasing slope (down): When
arr[i] < arr[i-1], keep incrementing down. Add candies accordingly.
- Increasing slope (up): When
- To avoid double-counting the peak (where up and down meet),
subtract Math.min(up, down). - Continue until the end and return ans.
Time & Space Complexity:
Time Complexity: O(n)
Space Complexity: O(1)
Dry Run
Input: arr = [1, 0, 2]
Step 0: Start Function: candy(arr) arr = [1, 0, 2] n = 3 ans = n = 3 i = 1 Iteration (i = 1): - Check arr[1] === arr[0] → 0 === 1 ? false - up = 0 - Increasing slope? while(i < 3 && arr[i] > arr[i-1]) → 0 > 1 ? false - down = 0 - Decreasing slope? i=1, arr[1]=0, arr[0]=1 → 0 < 1 → true → down = 1, ans = 4, i = 2 - Next check: arr[2]=2, arr[1]=0 → 2 < 0 ? false - Update ans = 4 - min(up, down) = 4 - min(0,1) = 4 Iteration (i = 2): - Check arr[2] === arr[1] → 2 === 0 ? false - up = 0 - Increasing slope? i=2, arr[2]=2, arr[1]=0 → 2 > 0 → true → up = 1, ans = 5, i = 3 - Loop ends (i == n) - down = 0 (no check, since i = n) - Update ans = 5 - min(up, down) = 5 - min(1,0) = 5 Step 3: End Return ans = 5
Output: 5
var candy = function(arr) {
let n = arr.length;
let ans = n;
let i = 1;
while(i < n){
if(arr[i] === arr[i-1]) {
++i;
continue;
}
let up = 0;
while(i < n && arr[i] > arr[i-1]){
++up;
ans = ans + up;
++i;
}
let down = 0;
while(i < n && arr[i] < arr[i-1]) {
++down;
ans += down;
++i;
}
ans = ans - Math.min(up, down);
}
return ans;
};
def candy(arr):
n = len(arr)
ans = n
i = 1
while i < n:
if arr[i] == arr[i-1]:
i += 1
continue
up = 0
while i < n and arr[i] > arr[i-1]:
up += 1
ans += up
i += 1
down = 0
while i < n and arr[i] < arr[i-1]:
down += 1
ans += down
i += 1
ans -= min(up, down)
return ans
public class Solution {
public static long candy(int[] arr) {
int n = arr.length;
long ans = n;
int i = 1;
while (i < n) {
if (arr[i] == arr[i - 1]) { ++i; continue; }
int up = 0;
while (i < n && arr[i] > arr[i - 1]) {
++up;
ans += up;
++i;
}
int down = 0;
while (i < n && arr[i] < arr[i - 1]) {
++down;
ans += down;
++i;
}
ans -= Math.min(up, down);
}
return ans;
}
public static void main(String[] args) {
int[] ratings = {1, 2, 2};
System.out.println(candy(ratings)); // expected 4
}
}
#include <bits/stdc++.h>
using namespace std;
long long candy(const vector& arr) {
int n = arr.size();
long long ans = n;
int i = 1;
while (i < n) {
if (arr[i] == arr[i-1]) { ++i; continue; }
int up = 0;
while (i < n && arr[i] > arr[i-1]) {
++up;
ans += up;
++i;
}
int down = 0;
while (i < n && arr[i] < arr[i-1]) {
++down;
ans += down;
++i;
}
ans -= min(up, down);
}
return ans;
}
int main() {
vector ratings = {1, 2, 2};
cout << candy(ratings) << endl;
return 0;
}
#include <stdio.h>
long candy(int arr[], int n) {
long ans = n;
int i = 1;
while (i < n) {
if (arr[i] == arr[i-1]) { ++i; continue; }
int up = 0;
while (i < n && arr[i] > arr[i-1]) {
++up;
ans += up;
++i;
}
int down = 0;
while (i < n && arr[i] < arr[i-1]) {
++down;
ans += down;
++i;
}
ans -= (up < down ? up : down);
}
return ans;
}
int main() {
int ratings[] = {1, 2, 2};
int n = sizeof(ratings)
printf("%ld\n", candy(ratings, n));
return 0;
}
using System;
class Solution {
public static long Candy(int[] arr) {
int n = arr.Length;
long ans = n;
int i = 1;
while (i < n) {
if (arr[i] == arr[i - 1]) { ++i; continue; }
int up = 0;
while (i < n && arr[i] > arr[i - 1]) {
++up;
ans += up;
++i;
}
int down = 0;
while (i < n && arr[i] < arr[i - 1]) {
++down;
ans += down;
++i;
}
ans -= Math.Min(up, down);
}
return ans;
}
static void Main() {
int[] ratings = {1, 2, 2};
Console.WriteLine(Candy(ratings));
}
}
