> For the complete documentation index, see [llms.txt](https://chunhthanhde.gitbook.io/leetcode-top-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chunhthanhde.gitbook.io/leetcode-top-interview/topic-1-array-string/015-candy.md).

# 135. Candy 🍬

**Difficulty**: `Hard` - **Tags**: `Greedy`, `Array`

## Description

There are `n` children standing in a row. Each child is assigned a rating value given in the `ratings` integer array.

You are giving candy to the children under the following conditions:

* Each child must have at least one piece of candy.
* Children with higher ratings (larger rating values) will receive more candy than their neighbors with lower ratings.

Return the minimum amount of candy you need to distribute to children.

## Examples

**Example 1:**

Input:

```python
ratings = [1,0,2]
```

Output:

```
5
```

Explanation: You can allocate candies to the first, second, and third child as follows:

* First child: 2 candies
* Second child: 1 candy
* Third child: 2 candies

**Example 2:**

Input:

```python
ratings = [1,2,2]
```

Output:

```
4
```

Explanation: You can allocate candies to the first, second, and third child as follows:

* First child: 1 candy
* Second child: 2 candies
* Third child: 1 candy

The third child gets 1 candy because it satisfies the conditions.

***

## Solution 💡

We can solve this problem using a **two-pass greedy approach**:

1. First pass: Traverse from left to right. For each child, if the current child has a higher rating than the previous child, give more candy.
2. Second pass: Traverse from right to left. For each child, if the current child has a higher rating than the next child, adjust the candy count to satisfy the condition.

### Java

```java
class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        
        // Step 1: Give each child 1 candy initially
        Arrays.fill(candies, 1);

        // Step 2: Traverse left to right
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

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

        // Sum up the total number of candies
        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }

        return totalCandies;
    }
}

```

## Time Complexity ⏳

* The time complexity is **O(n)** because we are traversing the array twice (left-to-right and right-to-left), where `n` is the length of the `ratings` array.

## Space Complexity 💾

* The space complexity is **O(n)** because we are using an extra array to store the number of candies for each child.

You can find the full solution [here](https://github.com/ChunhThanhDe/Leetcode-Top-Interview/blob/main/Topic%201%20Array%20-%20String/015%20Candy/Solution.java).