Candy Distribution

🎯

Candy Distribution

hardGREEDYAmazonGoogleFacebook

Imagine you are a teacher distributing candies to children standing in a line, where each child has a rating. You want to make sure that children with higher ratings than their neighbors get more candies, but you want to minimize the total candies given.

💡 This problem is a classic greedy algorithm challenge where beginners often struggle to realize that a single pass is not enough. The difficulty lies in satisfying local constraints from both directions simultaneously, which requires a two-pass approach rather than a naive one-pass or brute force solution.

📋

Problem Statement

Given an integer array ratings representing the rating of each child standing in a line, distribute candies to these children such that: 1. Each child must have at least one candy. 2. Children with a higher rating than their immediate neighbors must get more candies than those neighbors. Return the minimum number of candies you need to distribute.

1 ≤ n ≤ 10^51 ≤ ratings[i] ≤ 10^5

💡

Example

Input"[1, 0, 2]"

Output5

Distribute candies as [2, 1, 2]. The child with rating 0 gets 1 candy, rating 1 gets 2 candies, and rating 2 gets 2 candies.

Input"[1, 2, 2]"

Output4

Distribute candies as [1, 2, 1]. The second child has a higher rating than the first, so gets more candies. The third child has the same rating as the second, so can have fewer candies.

• All ratings equal → output should be n (each child gets 1 candy)
• Strictly increasing ratings → candies increase by 1 each child
• Strictly decreasing ratings → candies decrease by 1 each child from left to right
• Single child → output is 1

⚠️

Common Mistakes

Trying to solve with a single pass from left to right only

Fails to satisfy right neighbor constraints, leading to incorrect candy counts

✅ Add a second pass from right to left to fix violations

Not initializing candies with at least 1 candy per child

Violates problem requirement, may cause zero candies assigned

✅ Initialize candies array with 1 candy for each child

Updating candies without checking if update is needed (e.g., candies[i] <= candies[i-1])

Unnecessary updates cause infinite loops or incorrect results in brute force

✅ Only update candies if current count is not already sufficient

Using max(left2right[i], right2left[i]) incorrectly or forgetting to combine both arrays

Final candy distribution does not satisfy both neighbors, leading to wrong answer

✅ Take the maximum candy count from both passes for each child

Not testing edge cases like all equal ratings or strictly increasing/decreasing sequences

Code may fail or produce incorrect results on these inputs

✅ Always test and reason about edge cases before submitting

🧠

Brute Force (Repeated Adjustment Until Stable)

💡 This approach exists to build intuition by simulating the problem constraints directly, even though it is inefficient. It helps beginners understand the problem's requirements and why a naive approach fails.

Intuition

Start by giving each child one candy. Then repeatedly scan the array and adjust candies to satisfy the rating constraints until no changes are needed.

Algorithm

1. Initialize an array candies with 1 candy for each child.
2. Repeat until no changes occur:
3. For each child from left to right, if rating[i] > rating[i-1] and candies[i] <= candies[i-1], increase candies[i].
4. For each child from right to left, if rating[i] > rating[i+1] and candies[i] <= candies[i+1], increase candies[i].
5. Sum all candies and return the total.

💡 The repeated passes ensure both left and right neighbor constraints are met, but this can take many iterations to stabilize.

</>

Code

def candy(ratings):
    n = len(ratings)
    candies = [1] * n
    changed = True
    while changed:
        changed = False
        for i in range(1, n):
            if ratings[i] > ratings[i - 1] and candies[i] <= candies[i - 1]:
                candies[i] = candies[i - 1] + 1
                changed = True
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
                candies[i] = candies[i + 1] + 1
                changed = True
    return sum(candies)

# Driver code
if __name__ == '__main__':
    print(candy([1, 0, 2]))  # Output: 5
    print(candy([1, 2, 2]))  # Output: 4

Line Notes

candies = [1] * nInitialize candies so each child has at least one candy as per problem requirement

changed = TrueMark that a change was made, so another iteration is needed

for i in range(1, n)Left to right pass to fix violations where right child has higher rating

if ratings[i] > ratings[i - 1] and candies[i] <= candies[i - 1]Check if current child needs more candies than left neighbor

candies[i] = candies[i - 1] + 1Increase candies to satisfy constraint

for i in range(n - 2, -1, -1)Right to left pass to fix violations where left child has higher rating

return sum(candies)Sum all candies to get the minimum total required

import java.util.*;
public class Candy {
    public static int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 1; i < n; i++) {
                if (ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
                    candies[i] = candies[i - 1] + 1;
                    changed = true;
                }
            }
            for (int i = n - 2; i >= 0; i--) {
                if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                    candies[i] = candies[i + 1] + 1;
                    changed = true;
                }
            }
        }
        int sum = 0;
        for (int c : candies) sum += c;
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(candy(new int[]{1, 0, 2})); // 5
        System.out.println(candy(new int[]{1, 2, 2})); // 4
    }
}

Line Notes

Arrays.fill(candies, 1);Initialize candies array with 1 candy per child

boolean changed = true;Flag to track if any candy count changed in iteration

for (int i = 1; i < n; i++)Left to right pass to fix candy counts

if (ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1])Check if current child needs more candies than left neighbor

candies[i] = candies[i - 1] + 1;Increase candies to satisfy constraint

changed = true;Mark that a change was made

for (int i = n - 2; i >= 0; i--)Right to left pass to fix candy counts

return sum;Return total candies after stabilization

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> candies(n, 1);
    bool changed = true;
    while (changed) {
        changed = false;
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
                candies[i] = candies[i - 1] + 1;
                changed = true;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                candies[i] = candies[i + 1] + 1;
                changed = true;
            }
        }
    }
    return accumulate(candies.begin(), candies.end(), 0);
}

int main() {
    vector<int> ratings1 = {1, 0, 2};
    cout << candy(ratings1) << "\n"; // 5
    vector<int> ratings2 = {1, 2, 2};
    cout << candy(ratings2) << "\n"; // 4
    return 0;
}

Line Notes

vector<int> candies(n, 1);Initialize candies vector with 1 candy per child

bool changed = true;Flag to track if any candy count changed in iteration

for (int i = 1; i < n; i++)Left to right pass to fix candy counts

if (ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1])Check if current child needs more candies than left neighbor

candies[i] = candies[i - 1] + 1;Increase candies to satisfy constraint

changed = true;Mark that a change was made

for (int i = n - 2; i >= 0; i--)Right to left pass to fix candy counts

return accumulate(candies.begin(), candies.end(), 0);Sum all candies to get total

function candy(ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1);
    let changed = true;
    while (changed) {
        changed = false;
        for (let i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
                candies[i] = candies[i - 1] + 1;
                changed = true;
            }
        }
        for (let i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                candies[i] = candies[i + 1] + 1;
                changed = true;
            }
        }
    }
    return candies.reduce((a, b) => a + b, 0);
}

// Test cases
console.log(candy([1, 0, 2])); // 5
console.log(candy([1, 2, 2])); // 4

Line Notes

const candies = new Array(n).fill(1);Initialize candies array with 1 candy per child

let changed = true;Flag to track if any candy count changed in iteration

for (let i = 1; i < n; i++)Left to right pass to fix candy counts

if (ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1])Check if current child needs more candies than left neighbor

candies[i] = candies[i - 1] + 1;Increase candies to satisfy constraint

changed = true;Mark that a change was made

for (let i = n - 2; i >= 0; i--)Right to left pass to fix candy counts

return candies.reduce((a, b) => a + b, 0);Sum all candies to get total

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Each iteration scans the array twice (O(n)) and may repeat up to O(n) times in worst case, leading to O(n^2) time complexity.

💡 For n=20, this means up to 400 operations, which is slow but manageable for small inputs.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but helps understand the problem constraints and why optimization is needed.

🧠

Two-Pass Greedy with Left-to-Right and Right-to-Left Arrays

💡 This approach improves efficiency by using two passes to enforce constraints from both directions separately, then combining results. It is a classic greedy technique that beginners must master for array problems with neighbor constraints.

Intuition

Assign candies from left to right ensuring each child has more candies than the left neighbor if rating is higher. Then assign candies from right to left similarly. The final candies for each child is the max of the two passes.

Algorithm

1. Initialize two arrays left2right and right2left with 1 candy each.
2. Traverse ratings from left to right: if rating[i] > rating[i-1], left2right[i] = left2right[i-1] + 1.
3. Traverse ratings from right to left: if rating[i] > rating[i+1], right2left[i] = right2left[i+1] + 1.
4. For each child, assign candies as max(left2right[i], right2left[i]).
5. Sum all candies and return the total.

💡 The two arrays capture constraints from each direction independently, and taking max ensures both neighbors' conditions are met.

</>

Code

def candy(ratings):
    n = len(ratings)
    left2right = [1] * n
    right2left = [1] * n
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            left2right[i] = left2right[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            right2left[i] = right2left[i + 1] + 1
    return sum(max(left2right[i], right2left[i]) for i in range(n))

# Driver code
if __name__ == '__main__':
    print(candy([1, 0, 2]))  # Output: 5
    print(candy([1, 2, 2]))  # Output: 4

Line Notes

left2right = [1] * nInitialize candies from left pass with minimum 1 candy each

right2left = [1] * nInitialize candies from right pass with minimum 1 candy each

for i in range(1, n)Left to right pass to enforce increasing rating constraint

if ratings[i] > ratings[i - 1]Check if current rating is higher than left neighbor

left2right[i] = left2right[i - 1] + 1Assign one more candy than left neighbor

for i in range(n - 2, -1, -1)Right to left pass to enforce increasing rating constraint from right

if ratings[i] > ratings[i + 1]Check if current rating is higher than right neighbor

right2left[i] = right2left[i + 1] + 1Assign one more candy than right neighbor

sum(max(left2right[i], right2left[i]) for i in range(n))Combine both passes by taking max candies needed for each child

import java.util.*;
public class Candy {
    public static int candy(int[] ratings) {
        int n = ratings.length;
        int[] left2right = new int[n];
        int[] right2left = new int[n];
        Arrays.fill(left2right, 1);
        Arrays.fill(right2left, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left2right[i] = left2right[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right2left[i] = right2left[i + 1] + 1;
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.max(left2right[i], right2left[i]);
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(candy(new int[]{1, 0, 2})); // 5
        System.out.println(candy(new int[]{1, 2, 2})); // 4
    }
}

Line Notes

Arrays.fill(left2right, 1);Initialize left to right candies with 1 candy each

Arrays.fill(right2left, 1);Initialize right to left candies with 1 candy each

for (int i = 1; i < n; i++)Left to right pass to assign candies based on left neighbor

if (ratings[i] > ratings[i - 1])Check if current rating is higher than left neighbor

left2right[i] = left2right[i - 1] + 1;Assign one more candy than left neighbor

for (int i = n - 2; i >= 0; i--)Right to left pass to assign candies based on right neighbor

if (ratings[i] > ratings[i + 1])Check if current rating is higher than right neighbor

right2left[i] = right2left[i + 1] + 1;Assign one more candy than right neighbor

sum += Math.max(left2right[i], right2left[i]);Take max candies needed from both passes

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> left2right(n, 1);
    vector<int> right2left(n, 1);
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            left2right[i] = left2right[i - 1] + 1;
        }
    }
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            right2left[i] = right2left[i + 1] + 1;
        }
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += max(left2right[i], right2left[i]);
    }
    return sum;
}

int main() {
    vector<int> ratings1 = {1, 0, 2};
    cout << candy(ratings1) << "\n"; // 5
    vector<int> ratings2 = {1, 2, 2};
    cout << candy(ratings2) << "\n"; // 4
    return 0;
}

Line Notes

vector<int> left2right(n, 1);Initialize left to right candies with 1 candy each

vector<int> right2left(n, 1);Initialize right to left candies with 1 candy each

for (int i = 1; i < n; i++)Left to right pass to assign candies based on left neighbor

if (ratings[i] > ratings[i - 1])Check if current rating is higher than left neighbor

left2right[i] = left2right[i - 1] + 1;Assign one more candy than left neighbor

for (int i = n - 2; i >= 0; i--)Right to left pass to assign candies based on right neighbor

if (ratings[i] > ratings[i + 1])Check if current rating is higher than right neighbor

right2left[i] = right2left[i + 1] + 1;Assign one more candy than right neighbor

sum += max(left2right[i], right2left[i]);Take max candies needed from both passes

function candy(ratings) {
    const n = ratings.length;
    const left2right = new Array(n).fill(1);
    const right2left = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            left2right[i] = left2right[i - 1] + 1;
        }
    }
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            right2left[i] = right2left[i + 1] + 1;
        }
    }
    let sum = 0;
    for (let i = 0; i < n; i++) {
        sum += Math.max(left2right[i], right2left[i]);
    }
    return sum;
}

// Test cases
console.log(candy([1, 0, 2])); // 5
console.log(candy([1, 2, 2])); // 4

Line Notes

const left2right = new Array(n).fill(1);Initialize left to right candies with 1 candy each

const right2left = new Array(n).fill(1);Initialize right to left candies with 1 candy each

for (let i = 1; i < n; i++)Left to right pass to assign candies based on left neighbor

if (ratings[i] > ratings[i - 1])Check if current rating is higher than left neighbor

left2right[i] = left2right[i - 1] + 1;Assign one more candy than left neighbor

for (let i = n - 2; i >= 0; i--)Right to left pass to assign candies based on right neighbor

if (ratings[i] > ratings[i + 1])Check if current rating is higher than right neighbor

right2left[i] = right2left[i + 1] + 1;Assign one more candy than right neighbor

sum += Math.max(left2right[i], right2left[i]);Take max candies needed from both passes

⏱

Complexity

TimeO(n)

SpaceO(n)

Two linear passes over the array plus a final linear sum, total O(n) time. Two arrays of size n used for space.

💡 For n=100000, this means about 300000 operations, which is efficient and scalable.

Interview Verdict: Accepted

This is the standard optimal solution for this problem and should be coded in interviews.

🧠

Space Optimized Greedy (Single Array with One Pass and Backward Correction)

💡 This approach reduces space usage by using only one candies array and correcting it in a backward pass, demonstrating how to optimize space without losing clarity or correctness.

Intuition

First assign candies from left to right as before. Then traverse backward to fix any violations where a child has a higher rating than the next but fewer or equal candies, updating candies in place.

Algorithm

1. Initialize candies array with 1 candy each.
2. Traverse ratings left to right: if rating[i] > rating[i-1], candies[i] = candies[i-1] + 1.
3. Traverse ratings right to left: if rating[i] > rating[i+1] and candies[i] <= candies[i+1], update candies[i] = candies[i+1] + 1.
4. Sum all candies and return the total.

💡 The backward pass fixes violations in place, avoiding the need for a separate array.

</>

Code

def candy(ratings):
    n = len(ratings)
    candies = [1] * n
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
            candies[i] = candies[i + 1] + 1
    return sum(candies)

# Driver code
if __name__ == '__main__':
    print(candy([1, 0, 2]))  # Output: 5
    print(candy([1, 2, 2]))  # Output: 4

Line Notes

candies = [1] * nInitialize candies with minimum 1 candy per child

for i in range(1, n)Left to right pass to assign candies based on left neighbor

if ratings[i] > ratings[i - 1]Check if current rating is higher than left neighbor

candies[i] = candies[i - 1] + 1Assign one more candy than left neighbor

for i in range(n - 2, -1, -1)Right to left pass to fix violations in place

if ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]Check if current rating is higher than right neighbor but candy count is not enough

candies[i] = candies[i + 1] + 1Update candies to satisfy right neighbor constraint

return sum(candies)Sum all candies to get total

import java.util.*;
public class Candy {
    public static int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                candies[i] = candies[i + 1] + 1;
            }
        }
        int sum = 0;
        for (int c : candies) sum += c;
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(candy(new int[]{1, 0, 2})); // 5
        System.out.println(candy(new int[]{1, 2, 2})); // 4
    }
}

Line Notes

Arrays.fill(candies, 1);Initialize candies array with 1 candy each

for (int i = 1; i < n; i++)Left to right pass to assign candies based on left neighbor

if (ratings[i] > ratings[i - 1])Check if current rating is higher than left neighbor

candies[i] = candies[i - 1] + 1;Assign one more candy than left neighbor

for (int i = n - 2; i >= 0; i--)Right to left pass to fix violations in place

if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1])Check if current rating is higher than right neighbor but candy count is insufficient

candies[i] = candies[i + 1] + 1;Update candies to satisfy right neighbor constraint

return sum;Return total candies after correction

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> candies(n, 1);
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
            candies[i] = candies[i + 1] + 1;
        }
    }
    return accumulate(candies.begin(), candies.end(), 0);
}

int main() {
    vector<int> ratings1 = {1, 0, 2};
    cout << candy(ratings1) << "\n"; // 5
    vector<int> ratings2 = {1, 2, 2};
    cout << candy(ratings2) << "\n"; // 4
    return 0;
}

Line Notes

vector<int> candies(n, 1);Initialize candies vector with 1 candy each

for (int i = 1; i < n; i++)Left to right pass to assign candies based on left neighbor

if (ratings[i] > ratings[i - 1])Check if current rating is higher than left neighbor

candies[i] = candies[i - 1] + 1;Assign one more candy than left neighbor

for (int i = n - 2; i >= 0; i--)Right to left pass to fix violations in place

if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1])Check if current rating is higher than right neighbor but candy count is insufficient

candies[i] = candies[i + 1] + 1;Update candies to satisfy right neighbor constraint

return accumulate(candies.begin(), candies.end(), 0);Sum all candies to get total

function candy(ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
            candies[i] = candies[i + 1] + 1;
        }
    }
    return candies.reduce((a, b) => a + b, 0);
}

// Test cases
console.log(candy([1, 0, 2])); // 5
console.log(candy([1, 2, 2])); // 4

Line Notes

const candies = new Array(n).fill(1);Initialize candies array with 1 candy each

for (let i = 1; i < n; i++)Left to right pass to assign candies based on left neighbor

if (ratings[i] > ratings[i - 1])Check if current rating is higher than left neighbor

candies[i] = candies[i - 1] + 1;Assign one more candy than left neighbor

for (let i = n - 2; i >= 0; i--)Right to left pass to fix violations in place

if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1])Check if current rating is higher than right neighbor but candy count is insufficient

candies[i] = candies[i + 1] + 1;Update candies to satisfy right neighbor constraint

return candies.reduce((a, b) => a + b, 0);Sum all candies to get total

⏱

Complexity

TimeO(n)

SpaceO(n)

Two linear passes over the array with in-place updates, total O(n) time and O(n) space for candies array.

💡 For n=100000, this approach is efficient and uses minimal extra space.

Interview Verdict: Accepted

This is a space-optimized variant of the two-pass greedy solution, suitable for interviews where space matters.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the two-pass greedy approach (Approach 2) because it is optimal and clear.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Two-Pass Greedy with Two Arrays	O(n)	O(n)	No	N/A	Optimal solution to code in interviews
3. Space Optimized Greedy (Single Array)	O(n)	O(n)	No	N/A	Good to mention or code if space optimization is required

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem constraints and examples with the interviewer.Step 2: Describe the brute force approach to show understanding of constraints.Step 3: Explain the two-pass greedy approach as the optimal solution.Step 4: Code the two-pass or space optimized solution carefully.Step 5: Test your code with edge cases and explain your reasoning.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to identify the need for two passes, correctly implement the greedy logic, and optimize for time and space.

Common Follow-ups

• What if ratings can be negative? → The solution still works as comparisons remain valid.
• Can you do it in O(1) space? → Not without modifying input or losing clarity; O(n) is optimal for clarity.

💡 These follow-ups test your understanding of constraints and ability to optimize further or handle edge cases.

🔍

Pattern Recognition

When to Use

Use this pattern when: 1. You must assign values to elements in a sequence. 2. There are local constraints comparing neighbors. 3. The problem asks for minimum or maximum sum satisfying constraints. 4. A two-pass or multi-pass greedy approach is needed to satisfy bidirectional constraints.

Signature Phrases

'Each child must have at least one candy''Children with a higher rating get more candies than neighbors'

NOT This Pattern When

Problems that require global optimization with overlapping subproblems (DP) or sorting-based greedy without neighbor constraints.

Similar Problems

Assign Cookies - greedy allocation based on size and greed factorMinimum Number of Arrows to Burst Balloons - greedy interval coverageJump Game II - greedy with array traversal and local constraints

Practice

1. Consider the following Python function that returns the largest monotone increasing digits number less than or equal to n. What is the output when n = 332?

def monotoneIncreasingDigits(n: int) -> int:
    digits = list(map(int, str(n)))
    marker = len(digits)
    for i in range(len(digits) - 1, 0, -1):
        if digits[i] < digits[i - 1]:
            digits[i - 1] -= 1
            marker = i
    for i in range(marker, len(digits)):
        digits[i] = 9
    return int(''.join(map(str, digits)))

print(monotoneIncreasingDigits(332))

easy

A. 299

B. 329

C. 2999

D. 322

Solution

1. Step 1: Trace the loop from right to left

   Digits start as [3, 3, 2]. At i=2, digits[2]=2 < digits[1]=3, so digits[1] decrements to 2 and marker=2.

2. Step 2: Set digits from marker to end to 9

   Digits become [3, 2, 9]. Next, at i=1, digits[1]=2 < digits[0]=3, so digits[0] decrements to 2 and marker=1. Then digits from index 1 onward set to 9 -> [2, 9, 9].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final digits [2,9,9] form 299 which is largest monotone ≤ 332 [OK]

Hint: Decrement and set trailing digits to 9 for monotone fix [OK]

Common Mistakes:

• Stopping after first decrement without rechecking previous digits
• Not setting trailing digits to 9
• Returning intermediate digits without full fix

2. What is the time complexity of the optimal greedy solution using prefix sums and two pointers for the Gas Station (Circular) problem, given n stations?

medium

A. O(n²) because of nested loops over stations

B. O(n log n) due to sorting or binary search in prefix sums

C. O(n) because prefix sums allow constant time range queries and a single pass

D. O(n) but with O(n) extra space for prefix sums

Solution

1. Step 1: Analyze prefix sums computation

   Computing prefix sums takes O(2n) = O(n) time.

2. Step 2: Analyze the single pass check

   The loop checking prefix[i+n] - prefix[i] runs n times, each in O(1), total O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with prefix sums yields linear time [OK]

Hint: Prefix sums enable O(1) range queries, total O(n) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Thinking sorting is needed
• Confusing space with time complexity

3. Identify the bug in the following code snippet for the Task Scheduler problem:

medium

A. Line with 'if cnt + 1 <= 0:' should be 'if cnt + 1 < 0:' to avoid pushing zero counts

B. Line with 'time += cycle if not max_heap else n + 1' should always add cycle, not n+1

C. Line with 'for _ in range(n + 1):' should be 'for _ in range(n):' to match cooldown

D. Line with 'heapq.heapify(max_heap)' should be after the while loop

Solution

1. Step 1: Understand frequency decrement logic

   When a task count reaches zero, it should not be pushed back into the heap.

2. Step 2: Check condition for pushing back tasks

   The condition cnt + 1 <= 0 incorrectly pushes zero counts back, causing infinite loops or extra scheduling.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to cnt + 1 < 0 fixes the bug [OK]

Hint: Only push tasks back if remaining count is negative (still pending) [OK]

Common Mistakes:

• Pushing zero counts back causes infinite loops
• Miscounting cooldown cycles
• Incorrect loop ranges

4. Suppose now each cookie can be assigned to multiple children (reusable cookies). Which modification to the original greedy algorithm correctly computes the maximum number of content children?

hard

A. Sort both arrays and increment both pointers i and j on assignment as before

B. Use the brute force nested loops approach to try all assignments since greedy fails with reusable cookies

C. Sort greed array only and assign the largest cookie to each child without sorting cookies

D. Keep sorting arrays, but do not increment cookie pointer j when a cookie is assigned; only increment child pointer i

Solution

1. Step 1: Understand reuse effect

   Cookies can be assigned multiple times, so cookie pointer j should not advance on assignment.

2. Step 2: Modify greedy accordingly

   Keep sorting both arrays, but only increment child pointer i when a cookie satisfies a child; j stays to reuse the same cookie.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Not incrementing j allows cookie reuse [OK]

Hint: Do not advance cookie pointer on assignment for reuse [OK]

Common Mistakes:

• Incrementing both pointers breaks reuse
• Using brute force unnecessarily
• Ignoring sorting leads to suboptimal matches

5. Suppose the problem is changed so that some people can be assigned to either city multiple times (reusable assignments), or the number of people sent to each city is not fixed. Which approach correctly adapts the solution?

hard

A. Use a dynamic programming approach to handle variable counts and reuse assignments

B. Use the same greedy sorting by cost difference and assign exactly n people to each city

C. Sort by absolute cost to city A and assign all to city A to minimize cost

D. Assign people greedily without sorting, picking the cheaper city for each person

Solution

1. Step 1: Understand problem change

   Allowing reuse or variable counts breaks the fixed half assignment constraint, invalidating the greedy approach.

2. Step 2: Why DP is needed

   Dynamic programming can explore all valid assignments with reuse or variable counts, ensuring minimal total cost under new constraints.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails when constraints are relaxed; DP handles complex state space [OK]

Hint: Relaxed constraints require DP, not greedy [OK]

Common Mistakes:

• Applying greedy unchanged despite constraint changes
• Ignoring reuse possibility in assignment
• Assuming sorting by absolute cost suffices