Baozi Training Leetcode solution 135: Candy
- 2019 年 11 月 10 日
- 筆記
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/
Problem Statement
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:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
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
Video Tutorial
You can find the detailed video tutorial here
- Youtube
- B站
Thought Process
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.
- Left to right pass: Ensure I have more points than my left neighbor if my ranking is higher. Else I just have 1 candy (this is minimum)
- Right to left pass: Ensure I have more points than my right neighbor if my ranking is higher.
Solutions
Naive solution
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
Two pass linear solution
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
References
- Leetcode discussion solution
