Candy Distribution

📋

Problem

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.

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

Edge cases: All ratings equal → output should be n (each child gets 1 candy)Strictly increasing ratings → candies increase by 1 each childStrictly decreasing ratings → candies decrease by 1 each child from left to right

</>

IDE

def candy(ratings: list[int]) -> int:public int candy(int[] ratings)int candy(vector<int> &ratings)function candy(ratings)

def candy(ratings):
    # Write your solution here
    pass

class Solution {
    public int candy(int[] ratings) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int candy(vector<int> &ratings) {
    // Write your solution here
    return 0;
}

function candy(ratings) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: n (e.g., 3 for [1,2,3])Assigning 1 candy to each child regardless of ratings, ignoring the requirement to give more candies to higher rated neighbors.✅ Implement two-pass greedy approach updating candies from left to right and right to left based on rating comparisons.

Wrong: Sum less than expected due to treating equal ratings as requiring more candiesIncorrectly increasing candies for children with equal ratings as neighbors.✅ Only increase candies when rating is strictly greater than neighbor, not equal.

Wrong: Incorrect candy counts at local maxima or minima (e.g., too few candies at peaks)Using single pass greedy approach that fails to adjust candies correctly at peaks and valleys.✅ Use two-pass approach to ensure candies assigned correctly from both directions.

Wrong: Runtime error or wrong output on empty inputNot handling empty input array, causing index errors or invalid operations.✅ Add explicit check for empty input and return 0 immediately.

Wrong: Timeout on large inputsUsing repeated adjustment or nested loops leading to O(n^2) complexity.✅ Implement O(n) two-pass greedy solution to pass performance constraints.

✓

Test Cases

Focus on handling boundary conditions like empty and single-element inputs.

Consider tricky cases with equal ratings and local peaks/valleys to catch subtle bugs.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"ratings":[1,0,2]}

Expected5

⏱ Performance - must finish in 2000ms

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. Total candies = 5.

💡 Consider assigning candies based on ratings compared to neighbors.

💡 Use two passes: left to right and right to left to ensure conditions.

💡 Assign candies as the maximum of left-to-right and right-to-left passes, adding one when rating is higher than neighbor.

Why it failed: Failed basic case: likely missed updating candies in both directions or incorrect comparison logic. Fix by implementing two-pass greedy approach ensuring candies[i] > neighbors if ratings[i] > neighbors.

✓ Correctly handles the canonical example with two-pass greedy approach.

t1_02basic

Input{"ratings":[1,2,2]}

Expected4

⏱ Performance - must finish in 2000ms

Distribute candies as [1, 2, 1]. The second child has higher rating than first, so gets more candies; the third child has equal rating to second, so gets 1 candy.

💡 Check how equal ratings affect candy distribution.

💡 Remember children with equal ratings do not require more candies than neighbors.

💡 Assign candies so that only strictly higher ratings get more candies than neighbors.

Why it failed: Incorrect output due to treating equal ratings as requiring more candies. Fix by ensuring candies only increase when rating is strictly greater than neighbor.

✓ Correctly handles equal ratings with proper candy assignment.

t2_01edge

Input{"ratings":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty input means no children, so zero candies needed.

💡 Consider what happens when there are no children.

💡 Check if your code handles empty arrays without errors.

💡 Return 0 immediately if ratings array is empty.

Why it failed: Fails on empty input by not handling zero-length array, causing errors or wrong output. Fix by adding a check for empty input and returning 0.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"ratings":[5]}

Expected1

⏱ Performance - must finish in 2000ms

Single child always gets 1 candy.

💡 What is the minimum candy for a single child?

💡 Ensure your code handles single-element arrays correctly.

💡 Return 1 candy for single child regardless of rating.

Why it failed: Fails single element case by returning 0 or more than 1 candy. Fix by initializing candies array with 1 for each child.

✓ Correctly returns 1 candy for single child.

t2_03edge

Input{"ratings":[1,2,3,4,5]}

Expected15

⏱ Performance - must finish in 2000ms

Strictly increasing ratings; candies assigned as [1,2,3,4,5], sum=15.

💡 Check how candies increase with strictly increasing ratings.

💡 Use left-to-right pass to assign increasing candies.

💡 Sum candies assigned as 1,2,3,... for increasing ratings.

Why it failed: Fails strictly increasing case by not increasing candies properly. Fix by ensuring candies[i] = candies[i-1] + 1 when ratings[i] > ratings[i-1].

✓ Correctly assigns increasing candies for strictly increasing ratings.

t2_04edge

Input{"ratings":[5,4,3,2,1]}

Expected15

⏱ Performance - must finish in 2000ms

Strictly decreasing ratings; candies assigned as [5,4,3,2,1], sum=15.

💡 Check how candies decrease with strictly decreasing ratings.

💡 Use right-to-left pass to assign decreasing candies.

💡 Sum candies assigned as 5,4,3,2,1 for decreasing ratings.

Why it failed: Fails strictly decreasing case by not updating candies in right-to-left pass. Fix by ensuring candies[i] = candies[i+1] + 1 when ratings[i] > ratings[i+1].

✓ Correctly assigns decreasing candies for strictly decreasing ratings.

t3_01corner

Input{"ratings":[1,3,4,5,2]}

Expected11

⏱ Performance - must finish in 2000ms

Greedy trap: local max at 5 requires candies [1,2,3,4,1], sum=11.

💡 Beware of greedy approach assigning candies in one pass only.

💡 Use two passes to handle local maxima correctly.

💡 Assign candies as max of left-to-right and right-to-left passes.

Why it failed: Fails greedy trap by assigning candies only in one pass, missing local maxima adjustments. Fix by implementing two-pass approach to handle peaks.

✓ Correctly handles local maxima with two-pass greedy.

t3_02corner

Input{"ratings":[1,2,2,3,2,1]}

Expected10

⏱ Performance - must finish in 2000ms

Tests handling equal ratings and local dips; candies assigned as [1,2,1,3,2,1], sum=10.

💡 Check how equal ratings affect candy assignment.

💡 Ensure candies do not increase for equal ratings.

💡 Use max of left-to-right and right-to-left passes for correct assignment.

Why it failed: Fails by increasing candies for equal ratings or missing right-to-left pass corrections. Fix by ensuring candies only increase for strictly greater ratings and using two passes.

✓ Correctly handles equal ratings and local dips.

t3_03corner

Input{"ratings":[1,2,3,2,3,4,1]}

Expected13

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in peaks and valleys; candies assigned as [1,2,3,1,2,3,1], sum=13.

💡 Check boundary conditions at peaks and valleys.

💡 Verify candies assigned correctly on both passes.

💡 Ensure no off-by-one errors in candy increments.

Why it failed: Fails off-by-one errors causing incorrect candy counts at peaks/valleys. Fix by carefully comparing neighbors and updating candies accordingly in both passes.

✓ Correctly handles peaks and valleys without off-by-one errors.

t4_01performance

Input{"ratings":[1,2,3,4,5,6,7,8,9,10,10,9,8,7,6,5,4,3,2,1,1,2,3,4,5,6,7,8,9,10,10,9,8,7,6,5,4,3,2,1,1,2,3,4,5,6,7,8,9,10,10,9,8,7,6,5,4,3,2,1,1,2,3,4,5,6,7,8,9,10,10,9,8,7,6,5,4,3,2,1,1,2,3,4,5,6,7,8,9,10,10,9,8,7,6,5,4,3,2,1]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) two-pass greedy algorithm must complete within 2 seconds.

💡 Use O(n) two-pass greedy approach for efficiency.

💡 Avoid nested loops or repeated adjustments.

💡 Pre-allocate arrays and minimize operations inside loops.

Why it failed: TLE due to O(n^2) or repeated adjustment approach. Fix by implementing two-pass O(n) greedy solution.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Consider the following Python function implementing the optimal wiggle subsequence algorithm. What is the value of count after the loop finishes when the input is [1, 5, 4]?

def wiggleMaxLength(nums):
    if not nums:
        return 0
    count = 1
    last_diff = 0
    for i in range(1, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):
            count += 1
            last_diff = diff
    return count

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Trace loop iterations

   Input: [1, 5, 4] - i=1: diff=5-1=4 >0 and last_diff=0 ≤0 -> count=2, last_diff=4 - i=2: diff=4-5=-1 <0 and last_diff=4 ≥0 -> count=3, last_diff=-1

2. Step 2: Final count value

   After loop, count=3, which is the length of the longest wiggle subsequence.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Count increments twice for valid wiggles [OK]

Hint: Count increments on sign change of diff from last_diff

Common Mistakes:

• Off-by-one counting
• Ignoring initial count=1
• Not updating last_diff correctly

2. What is the time complexity of the optimal greedy solution that sorts the greed and cookie arrays before assigning cookies to children?

medium

A. O(n + m) because sorting is not needed if arrays are scanned directly

B. O(n * m) where n is number of children and m is number of cookies

C. O(n log n + m log m) due to sorting both arrays, then O(n + m) for assignment

D. O(n^2) because each child is compared to all cookies in worst case

Solution

1. Step 1: Identify sorting costs

   Sorting greed array of size n costs O(n log n), sorting cookies array of size m costs O(m log m).

2. Step 2: Analyze assignment loop

   Two pointers scan both arrays once, costing O(n + m).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting dominates complexity, linear scan is minor [OK]

Hint: Sorting dominates; assignment is linear [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Ignoring sorting cost
• Confusing linear scan with quadratic

3. Examine the following BFS-based code for Jump Game II. Which line contains a subtle bug that can cause incorrect jump counts or infinite loops?

medium

A. Line checking if next_pos == n - 1 to return jumps

B. Line incrementing jumps before processing current level

C. Line calculating furthest_jump without bounding by n-1

D. Line adding next_pos to visited set

Solution

1. Step 1: Identify furthest_jump calculation

   furthest_jump = pos + nums[pos] can exceed array bounds, causing range() to go out of range or runtime error.

2. Step 2: Check impact

   Without min(pos + nums[pos], n - 1), code may attempt invalid indices, causing incorrect behavior or crashes.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bounding furthest_jump by n-1 prevents out-of-range errors [OK]

Hint: Always bound jump indices within array length [OK]

Common Mistakes:

• Forgetting to limit furthest_jump to n-1
• Incrementing jumps incorrectly
• Missing visited set usage

4. What is the time complexity of the optimal min-heap based algorithm for finding the minimum number of platforms required for n trains?

medium

A. O(n²) due to nested loops checking all train pairs

B. O(n) because each train is processed once

C. O(n log n) due to sorting and heap operations for each train

D. O(n log k) where k is the maximum number of platforms needed

Solution

1. Step 1: Identify sorting cost

   Sorting n trains by arrival time costs O(n log n).

2. Step 2: Analyze heap operations

   Each train causes at most one push and one pop on the heap, each O(log n), so total O(n log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting + heap operations dominate complexity [OK]

Hint: Sorting + heap push/pop per train -> O(n log n) [OK]

Common Mistakes:

• Assuming O(n) ignoring sorting and heap costs
• Confusing heap size k with n for complexity
• Mistaking nested loops for optimal approach complexity

5. Suppose the problem is modified so that you can buy and sell the same stock multiple times on the same day (i.e., unlimited transactions including multiple buys and sells per day). Which of the following algorithmic changes correctly adapts the solution?

hard

A. Add all positive differences between consecutive prices and also consider zero differences as profitable

B. Sum all positive differences between consecutive days as before, no change needed

C. Use a dynamic programming approach to consider multiple transactions per day explicitly

D. Modify the code to add all positive differences between consecutive prices including zero differences

Solution

1. Step 1: Understand the new constraint

   Allowing multiple transactions per day does not change the fact that profit comes from positive price differences.

2. Step 2: Check if algorithm needs change

   Summing all positive consecutive differences already accounts for all profitable transactions, including multiple per day.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Algorithm already sums all positive increments, no modification needed [OK]

Hint: Unlimited transactions per day still sum positive differences [OK]

Common Mistakes:

• Adding zero or negative differences incorrectly
• Overcomplicating with DP when greedy suffices
• Thinking multiple transactions per day require new logic