C++ | Easy | Greedy | O (N) Solution with Comments
\nclass Solution {\npublic:\n    int candy(vector<int>& rat) {\n        int n = rat.size(), sum = 0;\n        vector<int> res(n, 1);  // initialize the resultan
```\nclass Solution {\npublic:\n    int candy(vector<int>& rat) {\n        int n = rat.size(), sum = 0;\n        vector<int> res(n, 1);  // initialize the resultant array with all elements 1 since each child will get minimum 1 candy\n        \n        if (n == 1) \n        {\n            return 1;\n        }\n        \n        // traverse the given ratings array and if the value of rat[i + 1] is greater than rat[i],\n        // then update the value of ans[i + 1] as ans[i] + 1\n        // this is to make sure higher rating one gets more than right neighbour\n        for(int i=0; i<n-1; i++)\n        {\n            if (rat[i+1] > rat[i]) \n            {\n                res[i+1] = res[i] + 1;\n            }\n        }\n        \n        // traverse the given array from the back and if the value of rat[i] > rat[i + 1] and the value of res[i] <= res[i + 1],\n        // then update the value of res[i] as res[i + 1] + 1\n        // this is to make sure higher rating one gets more than left neighbour\n        for (int i=n-2; i>=0; i--) \n        {\n            if (rat[i] > rat[i+1] && res[i] <= res[i+1]) \n            {\n                res[i] = res[i+1]+1;\n            }\n        \n            sum += res[i]; // increment the sum by res[i]\n        }\n        \n        sum += res[n-1]; // increment with last element as it was left earlier\n        \n        return sum; // return the resultant sum\n    }\n};\n```\n\n**Time Complexity: O(N)\nSpace Complexity: O(N)**
['Greedy', 'C', 'C++']