Greedy Solution [Java, Time: O(n), Space: O(n)]


#1

Algo: Fill aux DS with 1 candy per student. Compare left & right neighbors ranks in 2 scans and give just one more candy (to be greedy :stuck_out_tongue:)

public class Solution {
    public int candy(ArrayList<Integer> A) {
        int res = A.size(), n = A.size();
        if(n == 0)
            return 0;
        Integer[] distributeArr = new Integer[n];
        Arrays.fill(distributeArr, 1); //filling minimum 1 cholocate for each student
        
        for(int i=1; i<n; i++) {
            if(A.get(i) > A.get(i-1)) { //checking with left neighbor
                distributeArr[i] = distributeArr[i-1]+1;
            }
        }
    
        for(int i=n-2; i>=0; i--) {
            if(A.get(i) > A.get(i+1)) { //checking with right neighbor
                // give one more candy
                distributeArr[i] = Math.max(distributeArr[i], distributeArr[i+1]+1);
            }
        }
        // now return sum of distributed candies to all.
       // This is lambda of style of summation. you can just sum by for loop also.
        return Arrays.asList(distributeArr).stream().mapToInt(Integer::intValue).sum();
    }
}