# Candy
**Difficulty:** HARD
[External](https://leetcode.com/problems/candy)
Canonical: https://scaleengineer.com/dsa/problems/candy
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Mastercard](https://scaleengineer.com/companies/mastercard), [Uber](https://scaleengineer.com/companies/uber), [Yandex](https://scaleengineer.com/companies/yandex), [PhonePe](https://scaleengineer.com/companies/phonepe), [ConsultAdd](https://scaleengineer.com/companies/consultadd), [Tencent](https://scaleengineer.com/companies/tencent), [Teradata](https://scaleengineer.com/companies/teradata), [Urban Company](https://scaleengineer.com/companies/urban-company), [Komprise](https://scaleengineer.com/companies/komprise)
---
## Problem
There are `n` children standing in a line. Each child is assigned a rating value given in the integer array `ratings`.

You are giving candies to these children subjected to the following requirements:

* Each child must have at least one candy.
* Children with a higher rating get more candies than their neighbors.

Return _the minimum number of candies you need to have to distribute the candies to the children_.

**Example 1:**

**Input:** ratings = [1,0,2]
**Output:** 5
**Explanation:** You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

**Example 2:**

**Input:** ratings = [1,2,2]
**Output:** 4
**Explanation:** You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

**Constraints:**

* `n == ratings.length`
* `1 <= n <= 2 * 104`
* `0 <= ratings[i] <= 2 * 104`

# Approaches
## Brute Force
This approach directly simulates the process of satisfying the candy distribution rules. We start by giving each child one candy. Then, we make multiple passes over the children, correcting the number of candies whenever a rule is violated. We continue this process until a full pass occurs with no corrections needed, at which point we have found a stable and valid distribution.
**Time:** O(n^2) · **Space:** O(n)
**Pros:** Simple to understand and conceptualize.
**Cons:** Very inefficient, with a time complexity of O(n^2) in the worst case.; Likely to result in a 'Time Limit Exceeded' error on larger inputs.
### Explanation
The brute-force method involves initializing a `candies` array of the same size as `ratings`, with each child receiving one candy. We then enter a loop that continues as long as we are making changes to the candy allocation. Inside the loop, we iterate through each child and check if their candy allocation violates the rules with respect to their left and right neighbors. If a child has a higher rating than a neighbor but not more candies, we increment their candy count. This process is repeated until an entire pass over all children results in no changes, indicating that the rules are satisfied for everyone. The worst-case scenario for this approach is a long, strictly decreasing sequence of ratings, which would require `O(n)` passes, with each pass taking `O(n)` time.

```java
public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        boolean hasChanged = true;
        while (hasChanged) {
            hasChanged = false;
            for (int i = 0; i < n; i++) {
                if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
                    candies[i] = candies[i - 1] + 1;
                    hasChanged = true;
                }
                if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                    candies[i] = candies[i + 1] + 1;
                    hasChanged = true;
                }
            }
        }
        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }
        return totalCandies;
    }
}
```
### Algorithm
*   Initialize a `candies` array of size `n` with all elements set to 1. This ensures every child gets at least one candy.
*   Use a boolean flag, `hasChanged`, to track if any updates are made in a pass through the array.
*   Repeatedly loop through the `candies` array as long as `hasChanged` is true.
*   In each pass:
    *   Reset `hasChanged` to `false`.
    *   Iterate through the children from left to right.
    *   For each child `i`, check the two conditions:
        *   If `ratings[i] > ratings[i-1]` and `candies[i] <= candies[i-1]`, update `candies[i] = candies[i-1] + 1` and set `hasChanged = true`.
        *   If `ratings[i] > ratings[i+1]` and `candies[i] <= candies[i+1]`, update `candies[i] = candies[i+1] + 1` and set `hasChanged = true`.
*   The loop terminates when a full pass is completed with no changes to the `candies` array, which means all conditions are satisfied.
*   Finally, sum up all the values in the `candies` array to get the minimum total.

## Two-Pass Approach
A more efficient approach is to break the problem into two simpler subproblems. The number of candies a child receives depends on their neighbors on both the left and the right. We can satisfy these two sets of constraints in two separate passes over the `ratings` array.
**Time:** O(n) · **Space:** O(n)
**Pros:** Efficient with a linear time complexity of O(n).; Much faster than the brute-force approach and will pass for large inputs.; The logic is straightforward to implement.
**Cons:** Requires extra space of O(n) for the `candies` array.
### Explanation
This approach uses a single `candies` array and two passes to solve the problem efficiently. 

First, we do a left-to-right pass. We initialize everyone with one candy. Then, we iterate from the second child to the last. If a child's rating is higher than their left neighbor's, we give them one more candy than their left neighbor. This ensures the rule `ratings[i] > ratings[i-1] => candies[i] > candies[i-1]` is met.

However, this pass doesn't consider the right neighbor. For example, for `ratings = [1, 0, 2]`, the first pass would result in `candies = [1, 1, 2]`. This is incorrect because the first child has a higher rating than the second but does not have more candies.

To fix this, we perform a second, right-to-left pass. We iterate from the second-to-last child to the first. If a child's rating is higher than their right neighbor's, we update their candy count to be the maximum of its current value and one more than their right neighbor's candy count. This ensures the right-neighbor rule is also satisfied without violating the already-satisfied left-neighbor rule. After both passes, the `candies` array holds the minimum required candies for each child.

```java
public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);

        // Left to right pass
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // Right to left pass
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }
        return totalCandies;
    }
}
```
### Algorithm
*   Create an integer array `candies` of size `n` and initialize all its elements to 1.
*   **First Pass (Left to Right):** Traverse the `ratings` array from `i = 1` to `n-1`.
    *   If `ratings[i] > ratings[i-1]`, it means child `i` must have more candies than child `i-1`. Update `candies[i] = candies[i-1] + 1`.
    *   This pass ensures that the condition regarding the left neighbor is satisfied for all children.
*   **Second Pass (Right to Left):** Traverse the `ratings` array from `i = n-2` down to `0`.
    *   If `ratings[i] > ratings[i+1]`, child `i` must have more candies than child `i+1`. The current value `candies[i]` already satisfies the left-neighbor rule. To satisfy the right-neighbor rule as well, we take the maximum: `candies[i] = Math.max(candies[i], candies[i+1] + 1)`.
*   **Summation:** Calculate the sum of all elements in the `candies` array to get the total minimum candies required.

## One-Pass Approach with Constant Space
The most optimal solution involves a single pass over the `ratings` array and uses constant extra space. This approach calculates the total number of candies on the fly by analyzing the local trends in ratings, specifically by identifying ascending and descending slopes.
**Time:** O(n) · **Space:** O(1)
**Pros:** Extremely efficient in terms of both time and space.; Optimal solution with O(n) time and O(1) space complexity.
**Cons:** The logic is complex and can be difficult to reason about and implement correctly.; Prone to off-by-one errors due to the tricky conditions at peaks and valleys.
### Explanation
This advanced approach avoids any auxiliary arrays by cleverly calculating the sum in one go. We iterate through the ratings, treating them as a landscape of hills and valleys. We maintain counters for the length of the current upward slope (`up`) and downward slope (`down`).

When the slope is ascending, the candies required form an arithmetic progression `1, 2, 3, ...`. When the slope is descending, they also form a progression, but the peak where the ascent meets the descent requires special handling. The number of candies at the peak must be greater than both its neighbors. This means the peak's candy count is determined by the length of both the preceding `up` slope and the succeeding `down` slope.

The algorithm iterates once, and for each element, it decides the number of candies based on the current trend (uphill, downhill, or plateau) and the lengths of the slopes, adjusting the total sum accordingly. The key insight is that for a downhill slope, we not only add candies for the current child but may also need to retroactively add a candy to the peak of the hill if the downhill slope becomes longer than the uphill one.

```java
public class Solution {
    public int candy(int[] ratings) {
        if (ratings.length == 0) {
            return 0;
        }
        int totalCandies = 1;
        int up = 0, down = 0, peak = 0;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i - 1] < ratings[i]) {
                up++;
                peak = up;
                down = 0;
                totalCandies += 1 + up;
            } else if (ratings[i - 1] == ratings[i])  {
                peak = up = down = 0;
                totalCandies += 1;
            } else { // ratings[i-1] > ratings[i]
                up = 0;
                down++;
                // Add 1 for the current child, and 1 for each of the previous `down-1` children on the slope.
                // Also, add 1 for the peak if the downhill slope is longer than the uphill one.
                totalCandies += down + (peak >= down ? 0 : 1);
            }
        }
        return totalCandies;
    }
}
```
### Algorithm
*   The core idea is to view the `ratings` array as a sequence of hills (an ascent followed by a descent) and valleys.
*   We iterate through the array once, keeping track of the length of the current `up` slope and `down` slope.
*   Initialize `total_candies = 1`, `up = 0`, `down = 0`, and `peak = 0`.
*   Iterate from the second child (`i = 1`) to the end:
    *   **Uphill (`ratings[i] > ratings[i-1]`):** We are on an ascending slope. Reset `down` slope length, increment `up` slope length. The current child gets `up + 1` candies. Update the `peak` length and add `1 + up` to the total.
    *   **Plateau (`ratings[i] == ratings[i-1]`):** The slope is broken. Reset `up`, `down`, and `peak`. The current child gets 1 candy. Add 1 to the total.
    *   **Downhill (`ratings[i] < ratings[i-1]`):** We are on a descending slope. Reset `up` slope length, increment `down` slope length. The current child gets 1 candy. The children on the descending slope get `1, 2, ..., down` candies. The peak of the hill might need an extra candy if the `down` slope is longer than the `up` slope that preceded it. We add `down` to the total, and also add 1 extra for the peak if `down > peak`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int Candy(int[] ratings) {
        int n = ratings.Length;
        int[] left = new int[n];
        int[] right = new int[n];
        Array.Fill(left, 1);
        Array.Fill(right, 1);
        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.Max(left[i], right[i]);
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int candy(int[] ratings) {
    int n = ratings.length;
    int up = 0;
    int down = 0;
    int peak = 0;
    int candies = 1;
    for (int i = 1; i < n; i++) {
      if (ratings[i - 1] < ratings[i]) {
        up++;
        peak = up + 1;
        down = 0;
        candies += peak;
      } else if (ratings[i] == ratings[i - 1]) {
        peak = 0;
        up = 0;
        down = 0;
        candies++;
      } else {
        down++;
        up = 0;
        candies += down + (peak > down ? 0 : 1);
      }
    }
    return candies;
  }
}

```

### CPP

```cpp
class Solution { public: int candy ( vector < int >& ratings ) { int n = ratings . size (); vector < int > left ( n , 1 ); vector < int > right ( n , 1 ); for ( int i = 1 ; i < n ; ++ i ) { if ( ratings [ i ] > ratings [ i - 1 ]) { left [ i ] = left [ i - 1 ] + 1 ; } } for ( int i = n - 2 ; ~ i ; -- i ) { if ( ratings [ i ] > ratings [ i + 1 ]) { right [ i ] = right [ i + 1 ] + 1 ; } } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { ans += max ( left [ i ], right [ i ]); } return ans ; } };
```

### Python

```python
class Solution:
    def candy(self, ratings: List[int]) -> int: n = len(ratings) left = [1] * n right = [1] * n for i in range(1, n): if ratings[i] > ratings[i - 1]: left[i] = left[i - 1] + 1 for i in range(n - 2, - 1, - 1): if ratings[i] > ratings[i + 1]: right[i] = right[i + 1] + 1 return sum(max(a, b) for a, b in zip(left, right))

```