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.
1using System;
2
3public class Solution {
4 public int Candy(int[] ratings) {
5 int n = ratings.Length;
6 int[] candies = new int[n];
7 Array.Fill(candies, 1);
8 for (int i = 1; i < n; i++) {
9 if (ratings[i] > ratings[i - 1]) {
10 candies[i] = candies[i - 1] + 1;
11 }
12 }
13 for (int i = n - 2; i >= 0; i--) {
14 if (ratings[i] > ratings[i + 1]) {
15 candies[i] = Math.Max(candies[i], candies[i + 1] + 1);
16 }
17 }
18 int totalCandies = 0;
19 foreach (int candy in candies) {
20 totalCandies += candy;
21 }
22 return totalCandies;
23 }
24
25 static void Main() {
26 Solution sol = new Solution();
27 int[] ratings = {1, 0, 2};
28 Console.WriteLine(sol.Candy(ratings));
29 }
30}This C# implementation follows the two-pass method with the first pass managing increasing ratings from left to right, and the second pass managing decreasing ratings from right to left. Proper candy allocation is achieved using the `Math.Max` function to handle cases where the right-to-left pass must override the first pass assignments.
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)
1#include <iostream>
2#include <vector>
#include <algorithm>
using namespace std;
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> left(n, 1), right(n, 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 totalCandy = 0;
for (int i = 0; i < n; ++i) {
totalCandy += max(left[i], right[i]);
}
return totalCandy;
}
int main() {
vector<int> ratings = {1, 0, 2};
cout << candy(ratings) << endl;
return 0;
}For the C++ solution, two vectors `left` and `right` keep track of required candies due to left and right comparisons, respectively. The final candy count is computed by considering the maximum value at each index between the two vectors.