Candy Distribution

▶

Steps

setup

Initialize candies array

Create a candies array with the same length as ratings, initializing all values to 1 because each child must have at least one candy.

💡 Starting with one candy per child ensures the minimum requirement before any increments.

Line:

n = len(ratings)
candies = [1] * n

💡 Every child starts with one candy, forming the baseline for further increments.

traverse

Left-to-right traversal start

Start traversing the ratings array from index 1 to compare each rating with its left neighbor.

💡 This pass ensures children with higher ratings than their left neighbor get more candies.

Line:

for i in range(1, n):

💡 We will check if ratings[i] > ratings[i-1] to decide candy increments.

compare

Compare ratings[1] and ratings[0]

Compare rating 0 at index 1 with rating 1 at index 0. Since 0 is not greater than 1, candies[1] remains 1.

💡 No increment needed because the current rating is not higher than the left neighbor.

Line:

if ratings[i] > ratings[i - 1]:
    candies[i] = candies[i - 1] + 1

💡 Candy count stays the same when rating is not higher than the left neighbor.

traverse

Move pointer i to index 2

Advance pointer i to index 2 to compare ratings[2] with ratings[1].

💡 We continue the left-to-right pass to check if candies need to be incremented.

Line:

for i in range(1, n):

💡 Next comparison will determine if candies[2] should increase.

compare

Compare ratings[2] and ratings[1]

Compare rating 2 at index 2 with rating 0 at index 1. Since 2 > 0, increment candies[2] to candies[1] + 1 = 2.

💡 This step increases candies for a child with a higher rating than the left neighbor.

Line:

if ratings[i] > ratings[i - 1]:
    candies[i] = candies[i - 1] + 1

💡 Candies increase to maintain the rule that higher rating means more candies than left neighbor.

traverse

Left-to-right traversal complete

Completed the left-to-right pass. Candies array is now [1, 1, 2].

💡 First pass ensures children with higher ratings than left neighbors have more candies.

Line:

for i in range(1, n):
    if ratings[i] > ratings[i - 1]:
        candies[i] = candies[i - 1] + 1

💡 Partial candy distribution respects left neighbor rating comparisons.

traverse

Right-to-left traversal start

Start traversing from index n-2 (1) down to 0 to compare ratings[i] with ratings[i+1].

💡 This pass ensures children with higher ratings than their right neighbor have more candies.

Line:

for i in range(n - 2, -1, -1):

💡 We will check if ratings[i] > ratings[i+1] and candies[i] <= candies[i+1] to decide increments.

compare

Compare ratings[1] and ratings[2]

Compare rating 0 at index 1 with rating 2 at index 2. Since 0 is not greater than 2, no candy update needed.

💡 No increment because current rating is not higher than right neighbor.

Line:

if ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
    candies[i] = candies[i + 1] + 1

💡 No change needed when rating is not greater than right neighbor.

traverse

Move pointer i to index 0

Move pointer i to index 0 to compare ratings[0] and ratings[1].

💡 Continuing right-to-left pass to check candy updates.

Line:

for i in range(n - 2, -1, -1):

💡 Next comparison will determine if candies[0] should increase.

compare

Compare ratings[0] and ratings[1]

Compare rating 1 at index 0 with rating 0 at index 1. Since 1 > 0 and candies[0] <= candies[1], update candies[0] to candies[1] + 1 = 2.

💡 This step corrects candy counts to satisfy right neighbor condition.

Line:

if ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
    candies[i] = candies[i + 1] + 1

💡 Right-to-left pass fixes candy counts to maintain the rule for right neighbors.

traverse

Right-to-left traversal complete

Completed the right-to-left pass. Candies array is now [2, 1, 2].

💡 Both passes combined ensure all rating conditions are satisfied.

Line:

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

💡 Candy distribution now respects both left and right neighbor rating comparisons.

prune

Sum all candies

Sum the candies array [2, 1, 2] to get the total candies needed: 5.

💡 The sum represents the minimum candies to distribute satisfying all conditions.

Line:

return sum(candies)

💡 Final answer is the total candies after adjustments.

def candy(ratings):
    n = len(ratings)  # STEP 1
    candies = [1] * n  # STEP 1
    for i in range(1, n):  # STEP 2
        if ratings[i] > ratings[i - 1]:  # STEP 3,5
            candies[i] = candies[i - 1] + 1  # STEP 5
    for i in range(n - 2, -1, -1):  # STEP 7
        if ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:  # STEP 8,10
            candies[i] = candies[i + 1] + 1  # STEP 10
    return sum(candies)  # STEP 12

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

📊

Candy Distribution - Watch the Algorithm Execute, Step by Step

Watching each candy assignment and pointer movement reveals how the greedy approach ensures each child gets more candies than neighbors with lower ratings, which is hard to grasp from code alone.

initialize

1

0

1

1

1

2

Result: 0

compare

1

0

i

1

1

1

2

Result: 0

compare

1

0

i

1

1

1

2

Result: 0

compare

1

0

1

1

i

1

2

Result: 0

compare

1

0

1

1

i

2

2

Result: 0

traverse

1

0

1

1

2

2

Result: 0

compare

1

0

i

1

1

2

2

Result: 0

compare

1

0

i

1

1

2

2

Result: 0

compare

i

1

0

1

1

2

2

Result: 0

compare

i

2

0

1

1

2

2

Result: 0

traverse

2

0

1

1

2

2

Result: 0

record

2

0

1

1

2

2

Result: 5

Key Takeaways

✓ The two-pass greedy approach ensures candy distribution respects both left and right neighbor rating comparisons.

This insight is hard to see from code alone because the interplay of two passes and conditions is subtle without visualization.

✓ Initializing all candies to 1 is crucial as a baseline before any increments.

It guarantees the minimum candy per child and simplifies the logic for increments.

✓ The right-to-left pass corrects candy counts that the left-to-right pass alone cannot fix.

This step is essential to handle cases where a child has a higher rating than the right neighbor but was not assigned enough candies initially.

Practice

1. You are given an array representing daily stock prices. You want to maximize profit by making as many buy-sell transactions as you like, but you must sell before you buy again. Which algorithmic approach guarantees the optimal total profit?

easy

A. Greedy approach summing all positive price differences between consecutive days

B. Dynamic Programming with memoization to explore all buy-sell pairs

C. Single pass to find the maximum single buy-sell pair profit

D. Divide and conquer to split the array and combine profits

Solution

1. Step 1: Understand the problem constraints

   The problem allows unlimited transactions but requires selling before buying again, so multiple buy-sell pairs can be combined.

2. Step 2: Identify the approach that captures all profitable segments

   Summing all positive consecutive day price differences captures every profitable transaction, ensuring maximum total profit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Summing positive differences matches the optimal profit for all test cases [OK]

Hint: Sum all positive consecutive price differences [OK]

Common Mistakes:

• Trying to find only one best buy-sell pair
• Using complex DP when greedy suffices
• Ignoring multiple transactions allowed

2. Given the following code for the Task Scheduler, what is the returned value for leastInterval(['A','A','B'], 2)?

easy

A. 3

B. 5

C. 6

D. 4

Solution

1. Step 1: Initialize frequencies and max-heap

   Tasks: A(2), B(1). Max-heap: [-2, -1].

2. Step 2: Simulate scheduling cycles

   Cycle 1: pop -2 (A), decrement to -1 and store; pop -1 (B), decrement to 0 ignore; cycle=2, heap not empty -> time += n+1=3.
   Cycle 2: pop -1 (A), decrement to 0 ignore; cycle=1, heap empty -> time += cycle=1.
   Total time = 3 + 1 = 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual simulation matches 4 units [OK]

Hint: Count cycles and add idle if heap not empty [OK]

Common Mistakes:

• Off-by-one in cycle count
• Adding n+1 even when heap empty
• Ignoring decrement of counts

3. The following code attempts to implement the peak-valley approach but contains a subtle bug. Identify the line causing incorrect profit calculation.

def maxProfit(prices):
    i = 0
    profit = 0
    n = len(prices)
    while i < n - 1:
        while i < n - 1 and prices[i] > prices[i + 1]:
            i += 1
        valley = prices[i]
        while i < n - 1 and prices[i] < prices[i + 1]:
            i += 1
        peak = prices[i]
        profit += peak - valley
    return profit

medium

A. Line with 'while i < n - 1 and prices[i] < prices[i + 1]:'

B. Line with 'valley = prices[i]'

C. Line with 'while i < n - 1 and prices[i] > prices[i + 1]:'

D. Line with 'profit += peak - valley'

Solution

1. Step 1: Compare with correct condition

   The correct condition should be prices[i] >= prices[i + 1] to skip equal or descending prices.

2. Step 2: Identify bug impact

   Using strict '>' misses equal prices, causing incorrect valley selection and possibly negative profit.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing '>' to '>=' fixes edge cases with flat prices [OK]

Hint: Check comparison operators in loops for off-by-one errors [OK]

Common Mistakes:

• Using strict inequalities causing missed equal prices
• Adding negative differences to profit
• Off-by-one errors causing index out of range

4. 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

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