We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Candies
  5. Discussions

Candies

Sort by

recency

|

673 Discussions

|

  • rajivaiyer
     + 0 comments

    My Java 8 solution, passing all test cases, for a Max Score of 50:

    The code is fairly simple & self-explanatory.

    public static long candies(int n, List<Integer> arr) {
        // Write your code here
        
        // dpL[i] = Min number of candies needed for child 'i' 
        //          when only considering the left neighbor constraint.

        // dpR[i] = Min number of candies needed for child 'i' 
        //          when only considering the right neighbor constraint.

        int[] dpL = new int[n];
        int[] dpR = new int[n];

        // Every child gets at least one candy.
        // Set dpL[i] = 1 and dpR[i] = 1 for all 'i'.
        Arrays.fill(dpL, 1);
        Arrays.fill(dpR, 1);

        // DP from Left to Right + DP from Right to Left in a Single Combined Loop
        for (int i = 1 , j = (n - 2) ; (i < n) || (j >= 0) ; i++, j--) {

            // DP from Left to Right
            if (i < n && arr.get(i) > arr.get(i - 1)) {
                dpL[i] = dpL[i - 1] + 1;
            }

            // DP from Right to Left
            if (j >= 0 && arr.get(j) > arr.get(j + 1)) {
                dpR[j] = dpR[j + 1] + 1;
            }

        }

        // Combine 'dpL' & 'dpR' results
        long minTotalCandies = 0;
        for (int i = 0; i < n; i++) {
            minTotalCandies += Math.max(dpL[i], dpR[i]);
        }

        return minTotalCandies;
    }

  • vs883140
     + 0 comments

    public static long candies(int n, List arr) { // Write your code here

        long[] candies = new long[n];
    Arrays.fill(candies, 1);

    for (int i=1; i<n; i++) {
        if (arr.get(i)>arr.get(i-1)) {
            candies[i] = candies[i-1]+1;
        }
    }

    for (int i=n-2; i>=0; i--) {
        if (arr.get(i)>arr.get(i+1)) {
            candies[i] = Math.max(candies[i], candies[i+1]+1);
        }
    }
    long sum = 0;
    for (long c : candies) {
        sum += c;
    }
    return sum;
}``

  • write2piyushkum1
     + 0 comments

    Java:

        public static long candies(int n, List<Integer> arr) {
        long[] candies = new long[n];
        Arrays.fill(candies, 1);
        // Left to right
        for (int i=1; i<n; i++) {
            if (arr.get(i)>arr.get(i-1)) {
                candies[i] = candies[i-1]+1;
            }
        }
        // Right to left
        for (int i=n-2; i>=0; i--) {
            if (arr.get(i)>arr.get(i+1)) {
                candies[i] = Math.max(candies[i], candies[i+1]+1);
            }
        }
        return Arrays.stream(candies).sum();
    }

  • lukegemmell16
     + 0 comments

    C++ Solution

    long long candies(unsigned n, vector<unsigned> arr) {
    vector<unsigned> candies(arr.size(), 1);
    
    for(unsigned i = 1; i < n; i++)
        if(arr[i] > arr[i-1])
            candies[i] = candies[i-1] + 1;
    
    for(int i = n - 2; i >= 0 ; i--)
        if(arr[i] > arr[i + 1])
            candies[i] = max(candies[i + 1] + 1, candies[i]);

    return accumulate(candies.begin(), candies.end(), static_cast<long long>(0));   
}

  • bawa101001
     + 0 comments

    Python solution 

    def candies(n, arr):
    # Write your code here
    total_candy = [1] * n
    for i in range(1, n):
        if arr[i] > arr[i - 1]:
            total_candy[i] = total_candy[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if arr[i] > arr[i + 1]:
            total_candy[i] = max(total_candy[i], total_candy[i + 1] + 1)
    
    # The result is the sum of all total_candy
    return sum(total_candy)