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)
                

No additional array used

def candies(n, arr): total = 1 peak_index=0 peak_value = 1 last_value = 1 i = 1 while iarr[j]: j +=1 i = j-1 j -=2 last_value = 1 total += last_value while j>=peak_index: if (arr[j]>arr[j+1]): last_value += 1 else: last_value=1 total += last_value j -= 1 total -= peak_value total -= last_value total += max(peak_value, last_value) last_value=1 i += 1

return total

RIP problem description. Extremely vague.

i know there are solution L-R and R-L solution , however for practice putepose I try to solve it different . But why do my code give wrong answer

def candies(n, arr):
    
    res = [1] * len(arr)
    i = 0
    
    while i < len(arr):
        
        if i == 0:
            if arr[i] < arr[i+1]:
                i += 1
                continue
        else:    
            if arr[i] > arr[i-1]:
                res[i] = res[i-1] + 1
        
        if not i == n-1 and arr[i] >= arr[i+1]:
            longest_decrease = 1
            j = i
            
            while True:
                if j == n-1 or arr[j] < arr[j+1] :
                    break
                if arr[j] > arr[j+1]:
                    longest_decrease += 1
                j += 1
        
            if not j == i:
                
                for ii in range(i, j+1):
                    res[ii] = max(res[ii], longest_decrease)
                    if ii == n - 1:
                        break
                    if arr[ii] == arr[ii+1]:
                        continue
                    longest_decrease -= 1
                    
                i = j
                
        i += 1
        
    return sum(res)

To solve this problem, we'll use a two-pass approach:

1. Left to Right Pass: Traverse the list from left to right. If a child has a higher rating than the previous child, increment the candy count for that child based on the previous child's candy count.

2. Right to Left Pass: Traverse the list from right to left. If a child has a higher rating than the next child, ensure that the current child's candy count is higher than the next child's candy count.

The final candy count for each child will be the maximum of the counts from the two passes.

Here's the PHP code to solve the "Candies" problem:

<?php

function candies($n, $ratings) {
    // Initialize candies array
    $candies = array_fill(0, $n, 1);
    
    // Left to right pass
    for ($i = 1; $i < $n; $i++) {
        if ($ratings[$i] > $ratings[$i - 1]) {
            $candies[$i] = $candies[$i - 1] + 1;
        }
    }
    
    // Right to left pass
    for ($i = $n - 2; $i >= 0; $i--) {
        if ($ratings[$i] > $ratings[$i + 1]) {
            $candies[$i] = max($candies[$i], $candies[$i + 1] + 1);
        }
    }
    
    // Calculate the total number of candies
    return array_sum($candies);
}

// Example usage:
$n = 5;
$ratings = [1, 0, 2, 1, 0];
echo candies($n, $ratings); // Output: 7

?>

Explanation

1. Initialization:

   • We initialize the candies array with 1 candy for each child since each child must get at least one candy.

2. Left to Right Pass:

   • Traverse the array from left to right. If a child’s rating is greater than the previous child's rating, the current child should get more candies than the previous child. Hence, update the candies count for the current child.

3. Right to Left Pass:

   • Traverse the array from right to left. If a child’s rating is greater than the next child's rating, ensure that the current child’s candy count is greater than the next child’s candy count by updating if necessary.

4. Summing Up:

   • Finally, sum up all the values in the candies array to get the total number of candies required.

This approach ensures that the distribution of candies meets the problem's constraints with a time complexity of (O(n)) and space complexity of (O(n)).