Two Java Solutions - O(n) space and O(1) space, Easy to read with inline comments


  • 1
    A

    My initial O(n) runtime, O(1) space solution
    Cursors require much fine tuning, and prune to mistakes. Harder to debug on the spot

    public int candy(int[] ratings) {
            int max = ratings.length;   // each child gets 1 candy
            int ascendingMark = 0;      // start of ascending mark; could be updated from asc or equal trend
            int diff = 0;
            int peakDiff = 0, descDiff = 0;
    
            for (int i = 1; i < ratings.length; i++) {
                // weird equal case requirement
                if (ratings[i-1] == ratings[i]) {
                    diff = 0;
                    peakDiff = 0;
                    ascendingMark = i;
    
                } else if (ratings[i-1] < ratings[i]) {
                    diff++;     // greater than prev increase
    
                    // ascending mark
                    ascendingMark = i;
                    max += diff;
                    peakDiff = diff;
    
                } else {
                    diff = 0;
                    // descending, pad prev with a layer of +[1,1,1...]
                    // all the way from latest ascending mark
                    descDiff = (i - ascendingMark - 1);
                    max += (i - ascendingMark - 1);
    
                    // only updates peak if right side catches up, < than peak already
                    if (peakDiff <= descDiff) {
                        max += descDiff - peakDiff + 1;
                        peakDiff = descDiff + 1;
                    }
                }
            }
    
            return max;
        }
    

    O(n) Two-Pass, O(n) Space solution, referenced from Top Voted solution.
    Much simpler logic and cleaner code

    public int candy(int[] ratings) {
            int[] candy = new int[ratings.length];
    
            // left scan; fill higher --> covers last
            for (int i = 1; i < ratings.length; i++) {
                if (ratings[i] > ratings[i-1]) {
                    candy[i] = candy[i-1] + 1;
                }
            }
    
            // right scan; fill higher <-- covers [0]
            for (int i = ratings.length-2; i >= 0; i--) {
                if (ratings[i+1] < ratings[i]) {
                    candy[i] = Math.max(candy[i], candy[i+1] + 1);
                }
            }
    
            int max = 0;
            for (int k : candy) {
                max += k;
            }
            // at least 1 candy per child
            return max + ratings.length;
        }
    

Log in to reply
 

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