Candy | Leetcode 135 | Brute, Better and Optimal Solution

You are given an integer array ratings representing the rating of each child standing in a line. You must give candies to these children following two rules:

1. Every child must have at least one candy.
2. Children with a higher rating than their immediate neighbor must receive more candies than that neighbor.

Return the minimum total number of candies required.

Here’s the [Problem Link] to begin with.

Example

Input:  ratings = [1, 0, 2]
Output: 5
One optimal distribution: [2, 1, 2]

Input:  ratings = [1, 2, 2]
Output: 4
One optimal distribution: [1, 2, 1]

The challenge is to satisfy both rules while minimizing the total candies.

BRUTE

Intuition and Approach

A direct idea is to enforce the rule from both directions and then combine:

• Left to right pass ensures each child with a higher rating than the previous gets strictly more candies than the left neighbor.
• Right to left pass ensures each child with a higher rating than the next gets strictly more candies than the right neighbor.
• For each position, take the maximum of the two directional requirements to satisfy both neighbors.

This uses two arrays to store the minimum candies required when considering each direction separately.

Code Implementation

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        left = [-1] * n
        right = [-1] * n

        # Every child gets at least 1 candy from the left perspective
        left[0] = 1
        right[-1] = 1

        curr_rating = 1
        # Left to right: ensure increasing slopes get more than left neighbor
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                curr_rating += 1
            else:
                curr_rating = 1
            left[i] = curr_rating

        # Right to left: ensure decreasing slopes get more than right neighbor
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                curr_rating += 1
            else:
                curr_rating = 1
            right[i] = curr_rating

        # Combine both constraints
        answer = 0
        for i in range(n):
            answer += max(left[i], right[i])
        return answer

Code explanation

• Build left where left[i] is the minimum candies needed to satisfy the left neighbor rule up to i.
• Build right where right[i] is the minimum candies needed to satisfy the right neighbor rule from the right side.
• For each child, the final candies must be at least the maximum of these two requirements.
• Sum the maxima to get the total.

Time and Space Complexity

• Precise: two linear passes and one combine pass give O(n + n + n) time, arrays use O(n + n) space
• Simplified: O(n) time and O(n) space

Conclusion

The two arrays method is simple and mirrors the problem constraints directly. It is easy to reason about but uses extra memory.

BETTER

Intuition and Approach

We can keep the same logic but save memory by:

• Keeping only the left to right array.
• Performing the right to left sweep on the fly and aggregating the total using a running variable that represents the right side requirement at the current index.

This reduces auxiliary space while preserving correctness.

Code Implementation

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)

        # Left pass requirement
        left = [-1] * n
        left[0] = 1
        curr_rating = 1
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                curr_rating += 1
            else:
                curr_rating = 1
            left[i] = curr_rating

        # Right pass aggregated on the fly
        curr = 1      # candies needed from right perspective at current i
        right = 1     # previous right requirement
        total = max(1, left[n - 1])  # last index contribution

        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                curr = right + 1
            else:
                curr = 1
            total = total + max(left[i], curr)
            right = curr

        return total

Code explanation

• Compute left[i] with a single forward pass.
• Traverse backward and track the candies needed to satisfy the right neighbor rule as curr.
• At each index, the required candies are max(left[i], curr).
• Accumulate into total without storing an entire right array.

Time and Space Complexity

• Precise: two linear passes and O(1) extra variables besides left give O(n + n) time and O(n + 1) space
• Simplified: O(n) time and O(n) space

Conclusion

This approach keeps the clarity of the two pass method while saving one array. It is a practical improvement in memory usage.

OPTIMAL

Intuition and Approach

We can solve in one scan pattern by structuring the line into segments:

• An increasing slope where ratings strictly rise
• A decreasing slope where ratings strictly fall
• Equal neighbors as separators that reset the local requirement

While scanning once from left to right:

• For an increasing slope, increment a peak counter and add to total
• For a decreasing slope, increment a down counter and add to total
• If the down slope is longer than the up slope, compensate by adding the difference once to ensure the peak child has strictly more than both neighbors
• Equal ratings reset to a fresh segment with one candy

This counts candies for both slopes without extra arrays and fixes the peak overlap exactly once.

Code Implementation

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        total = 1
        i = 1

        while i < n:
            # flat neighbor, give 1 and continue
            if ratings[i] == ratings[i - 1]:
                total += 1
                i += 1
                continue

            # increasing slope
            peak = 1
            while i < n and ratings[i] > ratings[i - 1]:
                peak += 1
                total += peak
                i += 1

            # decreasing slope
            down = 1
            while i < n and ratings[i] < ratings[i - 1]:
                total += down
                down += 1
                i += 1

            # adjust if the downhill is longer than the uphill
            if down > peak:
                total += down - peak

        return total

Code explanation

• peak counts the length of the current increasing run and contributes 1, 2, 3, up to the peak height.
• down counts the length of the following decreasing run and contributes 1, 2, 3, along the descent.
• The child at the peak is counted in both runs, so if the descent is longer than the ascent, add a compensation down − peak to maintain the strict inequality on both sides.
• Equal ratings split runs and require only one candy for the new start.

Time and Space Complexity

• Precise: a single forward traversal with constant bookkeeping gives O(n) time and O(1) space
• Simplified: O(n) time and O(1) space

Conclusion

The slope counting technique achieves the optimal bounds with a single pass and constant space. It handles increases, decreases, and flats correctly and is ideal for large inputs.

Final takeaway

• Brute method uses two arrays and combines maxima for each child. Simple and clear, O(n) time and O(n) space.
• Better method removes one array by aggregating the right to left requirement on the fly. Still O(n) time and O(n) space.
• Optimal method counts up slopes and down slopes in a single pass with careful peak adjustment. O(n) time and O(1) space.

All three satisfy the problem rules. The optimal solution is recommended for production due to its speed and minimal memory use.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.