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 <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int candy(vector<int>& ratings) {
7 int n = ratings.size();
8 vector<int> candies(n, 1);
9 for (int i = 1; i < n; ++i) {
10 if (ratings[i] > ratings[i - 1]) {
11 candies[i] = candies[i - 1] + 1;
12 }
13 }
14 for (int i = n - 2; i >= 0; --i) {
15 if (ratings[i] > ratings[i + 1]) {
16 candies[i] = max(candies[i], candies[i + 1] + 1);
17 }
18 }
19 return accumulate(candies.begin(), candies.end(), 0);
20}
21
22int main() {
23 vector<int> ratings = {1, 0, 2};
24 cout << candy(ratings) << endl;
25 return 0;
26}In this C++ solution, we utilize the two-pass strategy by making the first pass from left to right, incrementing the candy count when a child has a higher rating than their left neighbor. The second pass is from right to left, ensuring higher ratings have more candies than right neighbors. The total number of candies is calculated using the `accumulate` function.
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)
1function
In the JavaScript solution, two arrays `left` and `right` are initialized to track each child's minimum candies required from left to right and right to left, respectively. The final candy count for each position is the maximum of the two approaches, ensuring constraints are satisfied.