Unique solution using sorting.
Question - \nYou are giving candies to these children subjected to the following requirements:\n\n- Each child must have at least one candy.\n- Children with a 
Question - \n**You are giving candies to these children subjected to the following requirements:**\n\n- Each child must have at least one candy.\n- Children with a higher rating get more candies than their neighbors.\n\nSo I thought, we can distribute candies to student with minimum ratings first, and if nearby childrens have candies, and they have lower rating than current student then we will take max of (1, 1 + candy on left, 1 + candy on right) for the current student\n\nBut you might think what if we haven\'t yet assigned the candy to neighbor childrens??\n- It will not happen as we are going in sorted order of rating. \n- So, if we are at some rating **x+1** and neaby childrens have rating **x**, it would have been already filled. \n- And if rating of nearby children is higher, then we just assign 1 candy to this student.\n\n```\n    int candy(vector<int>& ratings) {\n        vector<pair<int,int>> vec;\n        int n = ratings.size();\n        vec.reserve(n);\n        \n        for(int i = 0; i<n; i++){\n            vec.push_back({ratings[i], i});\n        }\n        \n        sort(vec.begin(), vec.end());\n        vector<int> candy(n, 0);\n        int ans = 0;\n        \n        for(int i = 0; i<n; i++){\n            int rating = vec[i].first;\n            int ind = vec[i].second;\n            \n            int candies = 1;\n            if(ind > 0 && ratings[ind] > ratings[ind-1]){\n                candies = max(candies, candy[ind-1] + 1);\n            }\n            if(ind < n-1 && ratings[ind] > ratings[ind+1]){\n                candies = max(candies, candy[ind+1] + 1);\n            }\n            ans += candies;\n            candy[ind] = candies;\n        }\n        \n        return ans;\n    }\n```\n\nI know there is a better complexity solution in *O(N) time*.\nJust thought to share a different approach. :)\n\n\nT.C. -> O(nlogn)\nS.C. -> O(n)\n\nIf something is not understood you can comment below \uD83D\uDC47\n
['Greedy', 'C', 'Sorting', 'C++']