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.
1import java.util.Arrays;
2
3public class CandyDistribution {
4 public static int candy(int[] ratings) {
5 int n = ratings.length;
6 int[] candies = new int[n];
7 Arrays.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 for (int candy : candies) {
20 totalCandies += candy;
21 }
22 return totalCandies;
23 }
24
25 public static void main(String[] args) {
26 int[] ratings = {1, 0, 2};
27 System.out.println(candy(ratings));
28 }
29}This Java implementation follows a strategy similar to the C and C++ solutions. The array `candies` is initialized such that each child receives one candy. Two linear passes then ensure each child has more candies than their neighbor if their rating is higher. The `Math.max` function helps with this check in the second pass.
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)
1class
The Python implementation similarly uses two lists, `left` and `right`, tracking the number of candies based on left-side and right-side conditions sequentially. The maximum value between the two arrays for each index yields the final candy distribution count.