Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Greedy

Candy

Hard · Greedy · Asked at Amazon, Google, Microsoft, Uber

Children stand in a line with ratings. Give each child at least one candy, and any child with a higher rating than an adjacent child must get more candies than that neighbour. Print the minimum total number of candies.

Input

First line: n. Second line: n space-separated integers.

Output

The minimum number of candies.

Constraints

Two passes: left to right (more than the left neighbour if the rating is higher), then right to left (more than the right neighbour), keeping the maximum of both requirements.

Example 1

Input

3
1 0 2

Output

5

Example 2

Input

3
1 2 2

Output

4

Hints

  1. Handle the two neighbours separately: one pass for the left neighbour, one for the right.
  2. Left to right: if rating[i] > rating[i−1], candy[i] = candy[i−1] + 1. Right to left: if rating[i] > rating[i+1], candy[i] = max(candy[i], candy[i+1] + 1).

Approach

Start everyone with 1 candy. The left-to-right pass satisfies every "higher than my left neighbour" constraint with the smallest possible numbers; the right-to-left pass does the same for the right neighbour while keeping what the first pass required (taking the maximum). Both constraints hold afterwards, and no value is larger than necessary, so the sum is minimal.

Complexity: O(n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    vector<long long> c(n, 1);
    for (int i = 1; i < n; i++)
        if (a[i] > a[i - 1]) c[i] = c[i - 1] + 1;
    for (int i = n - 2; i >= 0; i--)
        if (a[i] > a[i + 1]) c[i] = max(c[i], c[i + 1] + 1);
    cout << accumulate(c.begin(), c.end(), 0LL) << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
a = data[1 : 1 + data[0]]
n = len(a)
c = [1] * n
for i in range(1, n):
    if a[i] > a[i - 1]:
        c[i] = c[i - 1] + 1
for i in range(n - 2, -1, -1):
    if a[i] > a[i + 1]:
        c[i] = max(c[i], c[i + 1] + 1)
print(sum(c))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        long[] c = new long[n];
        Arrays.fill(c, 1);
        for (int i = 1; i < n; i++) if (a[i] > a[i - 1]) c[i] = c[i - 1] + 1;
        for (int i = n - 2; i >= 0; i--) if (a[i] > a[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
        long sum = 0;
        for (long x : c) sum += x;
        System.out.println(sum);
    }
}

Solve Candy online · All practice problems