I like to read this solution as a small machine: keep the useful information, throw away the noise. For 135. Candy, the solution in this repository is mainly a two pointers solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, sliding window, greedy.
The notes already sitting in the source point us in the right direction:
- Greedy
- TLE
- 47 / 48 test cases passed.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are candy, candies, left2right, right2left, count.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Greedy
02//TLE
03//47 / 48 test cases passed.
04class Solution {
05public:
06 int candy(vector<int>& ratings) {
07 int n = ratings.size();
08
09 int given = 0;
10 vector<int> candies(n);
11
12 int min_ele = *min_element(ratings.begin(), ratings.end());
13
14 for(int i = 0; i < ratings.size(); ++i){
15 if(ratings[i] == min_ele){
16 candies[i] = 1;
17 ++given;
18 }
19 }
20
21 // for(const int& candy : candies){
22 // cout << candy << " ";
23 // }
24 // cout << endl;
25
26 while(given < n){
27 for(int i = 0; i < n; ++i){
28 // cout << "i: " << i << endl;
29
30 if(candies[i]) continue;
31
32 int candy = 1;
33
34 if(i == 0 || ratings[i] <= ratings[i-1]){
35 //don't need to consider left
36 // cout << "a" << endl;
37 }else if(candies[i-1] != 0){
38 //it's left child is already given candy
39 candy = max(candy, candies[i-1]+1);
40 // cout << "b" << endl;
41 }else{
42 //must wait unitl child i-1 is given candy
43 // cout << "c" << endl;
44 continue;
45 }
46
47
48 if(i == n-1 || ratings[i] <= ratings[i+1]){
49 //don't need to consider right
50 // cout << "d" << endl;
51 }else if(candies[i+1] != 0){
52 //must consider right, and right is given candy
53 candy = max(candy, candies[i+1]+1);
54 // cout << "e" << endl;
55 }else{
56 //must consider right, but right is not given candy
57 // cout << "f" << endl;
58 continue;
59 }
60
61 candies[i] = candy;
62 ++given;
63 }
64 }
65
66 // for(const int& candy : candies){
67 // cout << candy << " ";
68 // }
69 // cout << endl;
70
71 return accumulate(candies.begin(), candies.end(), 0);
72 }
73};
74
75//Approach 1: Brute Force
76//TLE
77//47 / 48 test cases passed.
78//time: O(N^2), space: O(N)
79class Solution {
80public:
81 int candy(vector<int>& ratings) {
82 int n = ratings.size();
83
84 //give each child one candy at first time
85 vector<int> candies(n, 1);
86
87 bool stop = false;
88 while(!stop){
89 stop = true;
90 for(int i = 0; i < n; ++i){
91 if(i > 0 && ratings[i] > ratings[i-1]){
92 if(candies[i] <= candies[i-1]){
93 stop = false;
94 candies[i] = candies[i-1]+1;
95 }
96 }
97 if(i < n-1 && ratings[i] > ratings[i+1]){
98 if(candies[i] <= candies[i+1]){
99 stop = false;
100 candies[i] = candies[i+1]+1;
101 }
102 }
103 }
104 }
105
106 return accumulate(candies.begin(), candies.end(), 0);
107 }
108};
109
110//Approach 2: Using two arrays
111//Runtime: 40 ms, faster than 85.56% of C++ online submissions for Candy.
112//Memory Usage: 18.6 MB, less than 5.93% of C++ online submissions for Candy.
113//time: O(N), space: O(N)
114class Solution {
115public:
116 int candy(vector<int>& ratings) {
117 int n = ratings.size();
118
119 vector<int> left2right(n, 1);
120 vector<int> right2left(n, 1);
121
122 for(int i = 1; i < n; ++i){
123 if(ratings[i] > ratings[i-1]){
124 /*
125 left2right[i-1] is update before left2right[i],
126 so left2right[i-1] >= left2right[i],
127 so we don't need to write:
128 left2right[i] = max(left2right[i], left2right[i-1]+1);
129 */
130 left2right[i] = left2right[i-1]+1;
131 }
132 }
133
134 for(int i = n-2; i >= 0; --i){
135 if(ratings[i] > ratings[i+1]){
136 right2left[i] = right2left[i+1]+1;
137 }
138 }
139
140 int ans = 0;
141
142 for(int i = 0; i < n; ++i){
143 ans += max(left2right[i], right2left[i]);
144 }
145
146 return ans;
147 }
148};
149
150//Approach 3: Using one array
151//Runtime: 40 ms, faster than 85.56% of C++ online submissions for Candy.
152//Memory Usage: 18.1 MB, less than 5.93% of C++ online submissions for Candy.
153//time: O(N), space: O(N)
154class Solution {
155public:
156 int candy(vector<int>& ratings) {
157 int n = ratings.size();
158
159 vector<int> candies(n, 1);
160
161 for(int i = 1; i < n; ++i){
162 if(ratings[i] > ratings[i-1]){
163 candies[i] = candies[i-1]+1;
164 }
165 }
166
167 for(int i = n-2; i >= 0; --i){
168 if(ratings[i] > ratings[i+1]){
169 //here candies[i] could > candies[i+1], so we need the max(..., ...) here
170 candies[i] = max(candies[i], candies[i+1]+1);
171 }
172 }
173
174 return accumulate(candies.begin(), candies.end(), 0);
175 }
176};
177
178//Approach 4: Single Pass Approach with Constant Space, slope based
179//not understand
180//Runtime: 32 ms, faster than 98.43% of C++ online submissions for Candy.
181//Memory Usage: 17.5 MB, less than 5.93% of C++ online submissions for Candy.
182//time: O(N), space: O(1)
183class Solution {
184public:
185 int count(int n){
186 return n * (n+1) / 2;
187 }
188
189 int candy(vector<int>& ratings) {
190 int n = ratings.size();
191
192 if(n <= 1) return n;
193
194 int candies = 0;
195 int up = 0, down = 0;
196 int old_slope = 0, new_slope;
197
198 for(int i = 1; i < n; ++i){
199 if(ratings[i] > ratings[i-1]){
200 new_slope = 1;
201 }else if(ratings[i] == ratings[i-1]){
202 new_slope = 0;
203 }else{
204 new_slope = -1;
205 }
206
207 if((old_slope >0 && new_slope == 0) ||
208 (old_slope < 0 && new_slope >= 0)){
209 candies += count(up) + count(down) + max(up, down);
210 up = down = 0;
211 }
212
213 if(new_slope > 0){
214 ++up;
215 }else if(new_slope < 0){
216 ++down;
217 }else{
218 //new_slope == 0
219 ++candies;
220 }
221
222 old_slope = new_slope;
223 }
224
225 candies += count(up) + count(down) + max(up, down) + 1;
226
227 return candies;
228 }
229};
230
231//slope-based
232//https://leetcode.com/problems/candy/discuss/135698/Simple-solution-with-one-pass-using-O(1)-space
233//Runtime: 40 ms, faster than 85.56% of C++ online submissions for Candy.
234//Memory Usage: 17.5 MB, less than 5.93% of C++ online submissions for Candy.
235//time: O(N), space: O(1)
236class Solution {
237public:
238 int candy(vector<int>& ratings) {
239 int n = ratings.size();
240
241 if(n <= 1) return n;
242
243 //up: how many transitions are going up
244 int up = 0;
245 //down: how many transitions are going down
246 int down = 0;
247 //record the mountain peak
248 int peak = 0;
249
250 //candy for 0th child?
251 int ans = 1;
252
253 for(int i = 1; i < n; ++i){
254 if(ratings[i] > ratings[i-1]){
255 ++up;
256 peak = up;
257 down = 0;
258 //the mountain's foot must be >= 1
259 ans += (1+up);
260 }else if(ratings[i] == ratings[i-1]){
261 up = down = peak = 0;
262 ans += 1;
263 }else{
264 //ratings[i] < ratings[i-1]
265 ++down;
266 up = 0;
267 /*
268 consider [0,1,20,9,8,7],
269 when we are at 9, down = 1,
270 when we are at 8, down = 2,
271 when we are at 7, down = 3
272
273 actually 9 should have 3 candy,
274 8 should have 2 candy,
275 7 should have 1 candy,
276
277 we program as this because the sum are equivalent
278 */
279 ans += down;
280 if(peak < down){
281 /*
282 peak must >= down,
283 if it's smaller, we need to make it higher
284 */
285 ++ans;
286 }
287 }
288 }
289
290 return ans;
291 }
292};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.