leetcode

0 // original solution - accepted

1 class Solution {

2 public:

3 int candy(vector<int> &ratings) {

4 // place holder rating for easy neighbor calculation

5 ratings.insert(ratings.begin(), -1), ratings.push_back(-1);

6 int n = ratings.size();

7

8 // sort by rating remembering the original index

9 vector<pair<int, int>> vec;

10 vec.reserve(n);

11 for (int i = 1; i < n - 1; i++)

12 vec.push_back({ratings[i], i});

13 sort(vec.begin(), vec.end());

14

15 vector<int> res(n, 1); // 'Each child must have at least one candy'

16 res.front() = res.back() = 0; // except placeholders

17 for (auto &[rating, index] : vec) {

18 if (rating < ratings[index + 1]) res[index + 1] = max(res[index + 1], res[index] + 1);

19

20 if (rating < ratings[index - 1]) res[index - 1] = max(res[index - 1], res[index] + 1);

21 }

22

23 return accumulate(res.begin(), res.end(), 0);

24 }

25 };

26

27 // improved solution - same logic no nonsense

28 class Solution {

29 public:

30 int candy(vector<int> &ratings) {

31 int n = ratings.size();

32 if (n <= 1) return n;

33

34 vector<int> res(n, 1);

35 for (int i = 0; i < n - 1; i++) {

36 if (ratings[i] < ratings[i + 1]) res[i + 1] = res[i] + 1;

37 }

38

39 for (int i = n - 1; i > 0; i--) {

40 if (ratings[i] < ratings[i - 1]) res[i - 1] = max(res[i - 1], res[i] + 1);

41 }

42

43 return accumulate(res.begin(), res.end(), 0);

44 }

45 };