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
- 1 ≤ n ≤ 10^5
- 0 ≤ rating ≤ 2 · 10^4
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
- Handle the two neighbours separately: one pass for the left neighbour, one for the right.
- 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);
}
}