Leetcode solution 135: Candy
Blogger:https://blog.baozitraining.org/2019/11/leetcode-solution-135-candy.html
博客园: https://www.cnblogs.com/baozitraining/p/11747009.html
B站: https://www.bilibili.com/video/av73575024/
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
What is the minimum candies you must give?
Example 1:
Input: [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: [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.
Problem link
You can find the detailed video tutorial here
The straight forward idea is go through the ranking array, for each ranking, we try to make sure it has more points than its left and right neighbor. Note that it’s not going to work if you just do that because while you are increasing the values, it’s a chain effect that will affect the previous values as well, therefore we have to go all the way to the beginning.
Use below ranking as an example, assume everyone has 1 point already
Ranking: [5, 3, 1]
Points [1, 0, 0]
When at 5, [1, 0, 0]
When at 3, [2, 1, 0]
When at 1, [2, 2, 1]
you might think 5 points is enough, but it’s wrong. The culprit is when you at 1, and increase child at 3, you have the potential to break the assumption that child with 3 ranking always has less than its left neighbor if that neighbor has more points. Therefore, we have to go all the way to the beginning and comparison, thus resulting O(N^2) time complexity
That said, we have to go all the way to the beginning when we increase any value, so in the end it looks like [3, 2, 1]
Hint: if you cannot solve it in one pass, can we solve it in two passes?
A more clever thought is trying to distribute the candies in two passes. Previously we are trying to ensure at certain point both the left and right constrains should met. With two passes, namely first pass (from left to right) ensure all the left neighbors constrains are satisfied, and second pass ensures all the right neighbors contains are satisfied.
1 // O(N^2), exceeds time limit
2 public int candyON2(int[] ratings) {
3 if (ratings == null || ratings.length == 0) return 0;
4
5 if (ratings.length == 1) return 1;
6
7 int[] candies = new int[ratings.length];
8 candies[0] = 1;
9
10 for (int i = 1; i < ratings.length; i++) {
11 // if current rating is small, then we have to go back and increase previous candies if rating is larger
12 if (ratings[i] < ratings[i - 1]) {
13 int j = i - 1;
14 candies[i] = 1;
15 // This causes a chain of effect to go back to the beginning, the simple idea only increase the neighbor
16 // won't work, e.g, 5, 3, 1 should be 6 instead of 5
17 while (j >= 0 && ratings[j] > ratings[j + 1]) {
18 candies[j] += 1;
19 j--;
20 }
21
22 } else if (ratings[i] > ratings[i - 1]) {
23 candies[i] = candies[i - 1] + 1;
24 } else {
25 candies[i] = 1;
26 }
27 }
28
29 int count = 0;
30 for (int i = 0; i < candies.length; i++) {
31 count += candies[i];
32 }
33
34 return count;
35 }
Time Complexity: O(N^2)
Space Complexity: O(N) the extra candies array
1 public int candy(int[] ratings) {
2 if (ratings == null || ratings.length == 0) return 0;
3
4 int n = ratings.length;
5
6 if (n == 1) return 1;
7
8 int[] candies = new int[n];
9 candies[0] = 1;
10
11 // left -> right, if increasing, + 1, else just assign to 1, only change the values going forward
12 // not changing the values we already visited(left)
13 for (int i = 1; i < n; i++) {
14 if (ratings[i - 1] < ratings[i]) {
15 candies[i] = candies[i - 1] + 1;
16 } else {
17 candies[i] = 1;
18 }
19 }
20
21 // right -> left, if left is larger and candy is less, +1, not changing the right part, only changing the left
22 for (int i = n - 1; i >= 1; i--) {
23 if (ratings[i - 1] > ratings[i] && candies[i - 1] <= candies[i]) {
24 candies[i - 1] = candies[i] + 1;
25 }
26 }
27
28 int count = 0;
29 for (int i = 0; i < n; i++) {
30 count += candies[i];
31 }
32
33 return count;
34 }
Time Complexity: O(N)
Space Complexity: O(N) the extra candies array