Sponsored
Sponsored
The idea behind the Two-Pass Solution is to first ensure each child has more candies than the child before them if their rating is higher, and then make another pass to ensure the condition is also satisfied going from right to left. By leveraging two passes, we ensure that the candy distribution meets the requirements in both directions.
Time Complexity: O(n) - where n is the number of children, because we make two linear passes through the ratings.
Space Complexity: O(n) - where n is the number of children, due to the storage of candies array.
1#include <stdio.h>
2#include <string.h>
3
4int candy(int* ratings, int ratingsSize) {
5 int candies[ratingsSize];
6 memset(candies, 0, sizeof(candies));
7 for (int i = 0; i < ratingsSize; i++) {
8 candies[i] = 1;
9 }
10 for (int i = 1; i < ratingsSize; i++) {
11 if (ratings[i] > ratings[i - 1]) {
12 candies[i] = candies[i - 1] + 1;
13 }
14 }
15 for (int i = ratingsSize - 2; i >= 0; i--) {
16 if (ratings[i] > ratings[i + 1]) {
17 candies[i] = candies[i] > candies[i + 1] + 1 ? candies[i] : candies[i + 1] + 1;
18 }
19 }
20 int totalCandies = 0;
21 for (int i = 0; i < ratingsSize; i++) {
22 totalCandies += candies[i];
23 }
24 return totalCandies;
25}
26
27int main() {
28 int ratings[] = {1, 0, 2};
29 int size = sizeof(ratings) / sizeof(ratings[0]);
30 printf("%d\n", candy(ratings, size));
31 return 0;
32}This solution uses two passes over the ratings array.
In the first pass, we move from left to right, ensuring that each child has more candies than their left neighbor if they have a higher rating. In the second pass, we move from right to left, adjusting candies to maintain the higher-rating-more-candies constraint relative to their right neighbor. Finally, we sum up the candy totals.
This method involves the use of two arrays to maintain the candies given on left-to-right and right-to-left conditions separately. Instead of managing passes sequentially, we compute the required candies for each condition independently, and then derive the final candy count based on maximum requirements from both arrays at each index.
Time Complexity: O(n)
Space Complexity: O(n)
1using System;
2
public class Solution {
public int Candy(int[] ratings) {
int n = ratings.Length;
if (n <= 1) return n;
int[] left = new int[n];
int[] right = new int[n];
Array.Fill(left, 1);
Array.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 totalCandies = 0;
for (int i = 0; i < n; i++) {
totalCandies += Math.Max(left[i], right[i]);
}
return totalCandies;
}
static void Main() {
Solution sol = new Solution();
int[] ratings = {1, 0, 2};
Console.WriteLine(sol.Candy(ratings));
}
}The C# solution mirrors the Single-Pass with Two Arrays approach, using array fills for initial candy count and dealing with left and right rating comparison results separately to ensure compliance with problem constraints.