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. Given the following code and input, what is the final returned total cost?

def twoCitySchedCost(costs):
    costs.sort(key=lambda x: x[0] - x[1])
    n = len(costs) // 2
    total = 0
    for i, cost in enumerate(costs):
        if i < n:
            total += cost[0]
        else:
            total += cost[1]
    return total

costs = [[10,20],[30,200],[400,50],[30,20]]
print(twoCitySchedCost(costs))

easy

A. 110

B. 150

C. 120

D. 140

Solution

1. Step 1: Sort costs by difference cost[0] - cost[1]

   Differences: [10-20=-10, 30-200=-170, 400-50=350, 30-20=10]. Sorted: [[30,200], [10,20], [30,20], [400,50]]

2. Step 2: Assign first half to city A, rest to city B and sum costs

   First two: city A costs = 30 + 10 = 40; last two: city B costs = 20 + 50 = 70; total = 40 + 70 = 110

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum matches manual calculation [OK]

Hint: Sort by difference, assign first half to city A [OK]

Common Mistakes:

• Misordering after sorting by difference
• Off-by-one in loop boundary
• Adding wrong city cost for last half

2. The following code attempts to solve the Jump Game problem. Identify the line that contains a subtle bug that causes incorrect results on some inputs.

def canJump(nums):
    maxReach = 0
    for i, jump in enumerate(nums):
        # Bug: missing check if current index is beyond maxReach
        maxReach = max(maxReach, i + jump)
        if maxReach >= len(nums) - 1:
            return True
    return False

medium

A. Line 2: Initialization of maxReach

B. Line 3: for loop header enumerating nums

C. Line 4: Missing check if i > maxReach before updating maxReach

D. Line 6: Checking if maxReach reaches or exceeds last index

Solution

1. Step 1: Understand the missing condition

   The code does not check if the current index i is beyond maxReach, which means it may continue even when stuck.

2. Step 2: Identify the bug line

   Line 4 updates maxReach without verifying if i is reachable, causing false positives on inputs with unreachable indices.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding "if i > maxReach: return False" fixes the bug [OK]

Hint: Check if current index is reachable before updating maxReach [OK]

Common Mistakes:

• Forgetting to check i > maxReach
• Assuming maxReach update alone suffices

3. The following code attempts to remove k digits from a number string to get the smallest number. Which line contains a subtle bug that causes incorrect results on inputs with leading zeros?

def removeKdigits(num: str, k: int) -> str:
    builder = []
    for digit in num:
        while k > 0 and builder and builder[-1] > digit:
            builder.pop()
            k -= 1
        builder.append(digit)
    while k > 0:
        builder.pop()
        k -= 1
    result = ''.join(builder)  # Bug here
    return result if result else '0'

medium

A. Line where digits are popped inside the for loop

B. Line where leading zeros are not stripped from the final result

C. Line where remaining digits are popped after the loop

D. Line where digits are appended to builder

Solution

1. Step 1: Identify missing leading zero removal

   The code joins builder into a string but does not strip leading zeros, which can cause incorrect output like "0012" instead of "12".

2. Step 2: Why this is a bug

   Leading zeros must be removed to get the correct smallest number representation; otherwise, the output is invalid.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Adding .lstrip('0') fixes the bug [OK]

Hint: Always strip leading zeros before returning result [OK]

Common Mistakes:

• Forgetting to strip leading zeros
• Removing digits incorrectly in the loop
• Not popping remaining digits when k > 0

4. Suppose the Jump Game problem is modified so that you can jump backward as well as forward (i.e., jumps can be negative or positive). Which of the following approaches correctly determines if you can reach the last index from the first index under this new constraint?

hard

A. Use the original greedy approach tracking max reachable index, ignoring backward jumps

B. Use a breadth-first search (BFS) or graph traversal to explore all reachable indices including backward jumps

C. Use dynamic programming with memoization to recursively check reachability from each index

D. Sort the array and apply binary search to find reachable indices efficiently

Solution

1. Step 1: Understand the impact of backward jumps

   Backward jumps mean the problem is no longer monotonic; maxReach tracking fails as reachable indices can decrease.

2. Step 2: Identify suitable approach

   BFS or graph traversal explores all reachable indices in any direction, correctly handling negative jumps.

3. Step 3: Explain why other options fail

   Greedy fails due to backward jumps; DP recursion is possible but less efficient; sorting is irrelevant.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   BFS explores all reachable nodes regardless of jump direction [OK]

Hint: Backward jumps break greedy; BFS needed to explore all reachable indices [OK]

Common Mistakes:

• Trying to apply greedy despite backward jumps
• Assuming sorting helps reachability

5. Suppose the problem is modified so that the input list can contain negative integers as well. Which of the following approaches correctly adapts the algorithm to handle negatives and still produce the largest concatenated number?

hard

A. Convert negatives to positive strings before sorting with the comparator, then prepend '-' to those in final output

B. Filter out negative numbers since they cannot contribute to the largest concatenation

C. Separate negatives and positives, sort positives with comparator, sort negatives by absolute value descending, then concatenate positives followed by negatives

D. Convert all numbers to strings including negatives, then sort with the same comparator comparing concatenations

Solution

1. Step 1: Recognize negatives affect ordering and concatenation semantics

   Negative numbers cannot be treated the same as positives because concatenation with '-' changes lex order.

2. Step 2: Separate positives and negatives, sort positives with original comparator, sort negatives by absolute value descending

   Concatenate positives first (largest number), then negatives to maintain largest overall concatenation.

3. Step 3: This approach preserves ordering logic and handles negatives correctly

   Other options either ignore negatives or mishandle signs causing incorrect results.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Separating and sorting by sign handles negatives correctly [OK]

Hint: Negatives require separate handling, not just string comparison [OK]

Common Mistakes:

• Treating negatives as strings directly
• Ignoring negatives
• Converting negatives to positives incorrectly