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:
- Left-to-right pass → If a child has a
higher rating than the left neighbor, give them more candies than the neighbor. - Right-to-left pass → If a child has a
higher rating than the right neighbor, give them more candies than the neighbor. - Final answer → For each child, take the maximum candies required from both passes and sum them up.
Time & Space Complexity:
Time Complexity: O(n)
Space Complexity: O(n)
Dry Run
Input: arr = [1, 0, 2]
Step 0: Start Function: candy(arr) arr = [1, 0, 2] n = arr.length = 3 Initialize ltr = Array(n).fill(1) → [1, 1, 1] Step 1: Left-to-right pass (populate ltr) Iteration (i = 1): arr[1] = 0, arr[0] = 1 - Condition: 0 > 1 → false - ltr stays [1, 1, 1] Iteration (i = 2): arr[2] = 2, arr[1] = 0 - Condition: 2 > 0 → true - ltr[2] = ltr[1] + 1 = 1 + 1 = 2 - ltr becomes [1, 1, 2] Step 2: Right-to-left pass (populate rtl) Initialize rtl = Array(n).fill(1) → [1, 1, 1] Iteration (i = 1): arr[1] = 0, arr[2] = 2 - Condition: 0 > 2 → false - rtl stays [1, 1, 1] Iteration (i = 0): arr[0] = 1, arr[1] = 0 - Condition: 1 > 0 → true - rtl[0] = rtl[1] + 1 = 1 + 1 = 2 - rtl becomes [2, 1, 1] Step 3: Sum up using max(ltr[i], rtl[i]) ans = 0 i = 0: max(2, 1) = 2 → ans = 2 i = 1: max(1, 1) = 1 → ans = 3 i = 2: max(1, 2) = 2 → ans = 5 Step 4: End Return ans = 5
Output: 5
var candy = function(arr) {
let n = arr.length;
let ltr = Array(n).fill(1);
for(let i=1; i arr[i-1]){
ltr[i] = ltr[i-1] + 1;
}
}
let rtl = Array(n).fill(1);
for(let i=n-2; i>=0; i--){
if(arr[i] > arr[i+1]) {
rtl[i] = rtl[i+1] + 1;
}
}
let ans = 0;
for(let i=0; i < n; i++){
ans = ans + Math.max(rtl[i], ltr[i]);
}
return ans;
};
def candy(arr):
n = len(arr)
if n == 0:
return 0
ltr = [1] * n
rtl = [1] * n
for i in range(1, n):
if arr[i] > arr[i-1]:
ltr[i] = ltr[i-1] + 1
for i in range(n-2, -1, -1):
if arr[i] > arr[i+1]:
rtl[i] = rtl[i+1] + 1
ans = 0
for i in range(n):
ans += max(ltr[i], rtl[i])
return ans
if __name__ == "__main__":
print(candy([1, 0, 2]))
public class CandyProblem {
public static int candy(int[] arr) {
int n = arr.length;
if (n == 0) return 0;
int[] ltr = new int[n];
int[] rtl = new int[n];
for (int i = 0; i < n; i++) { ltr[i] = 1; rtl[i] = 1; }
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) ltr[i] = ltr[i - 1] + 1;
}
for (int i = n - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) rtl[i] = rtl[i + 1] + 1;
}
int ans = 0;
for (int i = 0; i < n; i++) ans += Math.max(ltr[i], rtl[i]);
return ans;
}
public static void main(String[] args) {
int[] ratings = {1, 0, 2};
System.out.println(candy(ratings));
}
}
#include <bits/stdc++.h>
using namespace std;
int candy(const vector& arr) {
int n = arr.size();
if (n == 0) return 0;
vector ltr(n, 1), rtl(n, 1);
for (int i = 1; i < n; ++i) {
if (arr[i] > arr[i-1]) ltr[i] = ltr[i-1] + 1;
}
for (int i = n - 2; i >= 0; --i) {
if (arr[i] > arr[i+1]) rtl[i] = rtl[i+1] + 1;
}
int ans = 0;
for (int i = 0; i < n; ++i) ans += max(ltr[i], rtl[i]);
return ans;
}
int main() {
vector ratings = {1, 0, 2};
cout << candy(ratings) << '\n';
return 0;
}
#include <stdio.h>
#include <stdlib.h>
int candy(int *arr, int n) {
if (n == 0) return 0;
int *ltr = (int*)malloc(sizeof(int) * n);
int *rtl = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) { ltr[i] = 1; rtl[i] = 1; }
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i-1]) ltr[i] = ltr[i-1] + 1;
}
for (int i = n - 2; i >= 0; i--) {
if (arr[i] > arr[i+1]) rtl[i] = rtl[i+1] + 1;
}
int ans = 0;
for (int i = 0; i < n; i++) ans += (ltr[i] > rtl[i] ? ltr[i] : rtl[i]);
free(ltr);
free(rtl);
return ans;
}
int main() {
int ratings[] = {1, 0, 2};
int n = sizeof(ratings) / sizeof(ratings[0]);
printf("%d\n", candy(ratings, n));
return 0;
}
using System;
class Program {
static int Candy(int[] arr) {
int n = arr.Length;
if (n == 0) return 0;
int[] ltr = new int[n];
int[] rtl = new int[n];
for (int i = 0; i < n; i++) { ltr[i] = 1; rtl[i] = 1; }
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) ltr[i] = ltr[i - 1] + 1;
}
for (int i = n - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) rtl[i] = rtl[i + 1] + 1;
}
int ans = 0;
for (int i = 0; i < n; i++) ans += Math.Max(ltr[i], rtl[i]);
return ans;
}
static void Main() {
int[] ratings = {1, 0, 2};
Console.WriteLine(Candy(ratings));
}
}
