> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/greedy/distribute-candy.md).

# Distribute Candy

There are **N** children standing in a line. Each child is assigned a rating value.

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

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

What is the minimum candies you must give?

**Input Format:**

```
The first and the only argument contains N integers in an array A.
```

**Output Format:**

```
Return an integer, representing the minimum candies to be given.
```

**Example:**

```
Input 1:
    A = [1, 2]

Output 1:
    3

Explanation 1:
    The candidate with 1 rating gets 1 candy and candidate with rating cannot get 1 candy as 1 is its neighbor. 
    So rating 2 candidate gets 2 candies. In total, 2 + 1 = 3 candies need to be given out.

Input 2:
    A = [1, 5, 2, 1]

Output 2:
    7

Explanation 2:
    Candies given = [1, 3, 2, 1]
```

```java
public class Solution {
    public int candy(ArrayList<Integer> A) {
        int n = A.size();
        if (n == 0)
            return 0;
        int[] candies = new int[n];
        Arrays.fill(candies, 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
                candies[i] = candies[i - 1] + 1;
        }

        for (int i = n - 2; i >= 0; i--) {
            if (A.get(i) > A.get(i + 1)) // checking with right neighbor
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
        int ans = 0;
        for (int x : candies)
            ans += x;
        return ans;
    }
}
```