Candy Distribution Algorithm

Here’s a greedy algorithm that solves the candy distribution problem:

int candy(vector<int>& rate) {
    int len = rate.size();
    int res = len;
    if (len <= 1) return res;
    vector<int> a(len, 0);
    
    // Ensure right neighbors are always greater than middle
    for(int i = 1; i < len; ++i) {
        if (rate[i] > rate[i-1])
            a[i] = a[i-1] + 1;
    }

    for(int i = len-1; i > 0; --i) {
        // Ensure left neighbors are always greater than middle  
        if (rate[i-1] > rate[i])
            a[i-1] = max(a[i-1], a[i]+1);  // Use max to avoid breaking right constraint
    }

    for(auto n : a)
        res += n;
    return res;
}

The algorithm works in two passes. First, we scan left to right ensuring each child with a higher rating than their left neighbor gets more candy. Then we scan right to left doing the same for right neighbors. The max function preserves previous constraints while adding new ones.

This runs in O(n) time and handles all edge cases correctly.

Buddy Strings Combination Sum Series