What is the brute force approach and complexity for Candy?

Start everyone at 1 and repeat sweeps until no neighbour rule is broken with time complexity O(N²) and space complexity O(N).

What is the optimal approach and complexity for Candy?

One pass for the left rule, one for the right rule; each child takes the larger value with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Candy?

Look for key signals in the prompt: "higher rating than its neighbours" indicates There is a rule for each adjacent pair, in both directions, so one walk is never enough.; "at least one candy" indicates Everyone starts at 1, so 1 is the lowest value we build from.; "minimum total" indicates We want the smallest value each child can have, which is why the max of the two walks is the answer..

Candy

Hard·LeetCode #135 Pro OnlyMedium

LeetCode

Problem Statement

There are n children standing in a line, and each child has a rating. You want to give out candy so that:

every child gets at least one candy, and
a child with a higher rating than a neighbour gets more candy than that neighbour.

Return the smallest total number of candies that meets both rules.

Input

An array ratings, where ratings[i] is the rating of child i.

Output

The minimum total number of candies.

Example 1

Input: ratings = [1, 0, 2]

Output: 5

Give 2, 1 and 2 candies. Child 0 and child 2 both have higher ratings than child 1, so each gets more than child 1.

Example 2

Input: ratings = [1, 2, 2]

Output: 4

Give 1, 2 and 1 candies. Child 1 is rated higher than child 0, so it gets more. Child 2 has the same rating as child 1, so the rule does not apply and 1 candy is enough.

Constraints

• 1 ≤ n ≤ 5 · 10^4
• n equals the length of `ratings`.
• 0 ≤ ratings[i] ≤ 5 · 10^4

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“higher rating than its neighbours”

→ There is a rule for each adjacent pair, in both directions, so one walk is never enough.

“at least one candy”

→ Everyone starts at 1, so 1 is the lowest value we build from.

“minimum total”

→ We want the smallest value each child can have, which is why the max of the two walks is the answer.

Approach Complexity Ladder

Brute Force — keep fixing broken pairsO(N²)O(N)

Start everyone at 1 and repeat sweeps until no neighbour rule is broken

Optimal — left pass, right pass, take the maxO(N)O(N)

One pass for the left rule, one for the right rule; each child takes the larger value

Brute Force Intuition

Give every child 1 candy. Sweep the line and check each pair. If a child who is rated higher has no more candy than a lower-rated neighbour, raise that child to one more than the neighbour. Repeat full sweeps until one sweep changes nothing. Then add up all the candy.

Recognition rule for this sub-pattern:

Keep a running balance; when it fails, the start must move past this point. Two passes handle left and right rules.

Remember this · Greedy

Trigger

Maximise count / minimise cost with a natural "best next step", sorting makes the choice obvious, reachability.

Think

Is there a choice I can always make safely without looking ahead?

Key question

Why can't the greedy choice be worse than the optimal one? (Try to break it with a small example.)

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Greedy translate into production architectures and low-level memory mechanics.

LLD Architecture