My answer was accepted, but can it be more intuitive?


  • 0
    G

    My answer was accepted, but the code has been tweaked several times before it's accepted. I wonder is there a simple and neat way to solve this problem that is so intuitive that you don't even need to tweak so many times before it is accepted?

    here is my code

    class Solution {
    public:
        int candy(vector<int> &ratings) {
            if (ratings.size() <= 1)
            {
                return ratings.size();
            }
            int diff = 0;
            int fast = 1;
            int slow = 0;
            int extra = 0;
            while(fast < ratings.size())
            {
                // go through the asccending ratings
                while(fast < ratings.size() && ratings[fast-1] < ratings[fast])
                {
                    ++fast;
                    if (!(fast < ratings.size() && ratings[fast-1] < ratings[fast]))
                    {
                        extra += (0+fast-1-slow)*(fast-slow)/2;
                        diff = fast-1-slow;
                        slow = fast-1;
                    }
                }
                // go through the descending ratings
                while(fast < ratings.size() && ratings[fast-1] > ratings[fast])
                {
                    ++fast;
                    if (!(fast < ratings.size() && ratings[fast-1] > ratings[fast]))
                    {
                        extra += (0+fast-1-slow-1)*(fast-slow-1)/2 + max(fast-1-slow-diff, 0);
                        slow = fast-1;
                    }
                }
                // go through the continuously equal ratings
                while(fast < ratings.size() && ratings[fast] == ratings[fast-1])
                {
                    ++fast;
                    if (!(fast < ratings.size() && ratings[fast] == ratings[fast-1]))
                    {
                        slow = fast-1;
                        diff = 0;
                    }
                }
            }
            return extra + ratings.size();
        }
    };

  • 3
    F

    I've got the solution with O(n) time complexity with O(constant) space in One pass with similar idea,

    Algorithm

    Start having given one candy to each kid i.e. sum = N candies to N children, Now, adjusting the sum in single pass. Repeat until End of ratings sequence

    1. Check increasing peak move until max-peak -> add the additional
      candies
    2. Check the decreasing of peak -> move to depression, add the
      additional candies for only the decreasing sequence after the
      peak
      ,
    3. Then check the range of decreasing & previous increasing sequence,
      adjust the max-peak candies [by adding additional candies to sum]
      only if the range of decreasing is > range of increasing and that would = (decreasing range - increasing range) [ otherwise, everything's in place, Note: you only need to adjust the peak if
      depression range is greater than inclination range]
    4. If it's flat [i.e adjacent ratings are same], just move on,
      everything's in place. [Note: the case where adjacent rating is
      same, it takes care of whether it's on top -peak or bottom, also
      since we're just moving on, it does not add additional candies
      than initial allotted unless it's declination which is handled in
      step 2] [i.e. example test case : [1, 3, 3, 2, 1] =>min no. candies
      = [1, 2, 3, 2, 1] , sum = 9 ]

    [PS: You need to know sum of numbers sequence 1 2, 3...n = (n * (n+1)) / 2, we need this when adjusting /adding number of candies in increasing or decreasing subsequence]


    I hope my code is elegant & readable enough....

    class Solution {
    public:
        int candy(vector<int> &ratings) {
            int n = ratings.size();
            int min_candies = n;
            
            int range = 0;
            for (size_t i = 0; i < n - 1; ) {
                int start = i;
                while (ratings[i] < ratings[i+1] && i < n-1) ++i;
                range = i - start;
                min_candies += (range * (range + 1)) / 2;
                if (i == n-1) break;
                
                start = i;
                while (ratings[i] > ratings[i+1] && i < n-1) ++i;
                int k = i - start - 1;
                min_candies += (k * (k + 1)) / 2;
                if (i - start > range) min_candies += (i - start - range);
                if (ratings[i] == ratings[i+1]) ++i;
            }
            return min_candies;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.