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 a list of non-negative integers and need to arrange them to form the largest possible number when concatenated. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming to find the maximum concatenation by exploring all subsequences

B. Sorting the numbers as strings using a custom comparator that compares concatenations

C. Greedy approach by always picking the largest integer first

D. Brute force generating all permutations and selecting the maximum concatenation

Solution

1. Step 1: Understand the problem requires ordering numbers to maximize concatenation

   The key is to compare pairs by concatenating in both possible orders and deciding which order yields a larger combined string.

2. Step 2: Recognize that sorting with a custom comparator based on concatenation comparisons guarantees optimal order

   This approach ensures the final concatenation is lexicographically largest, unlike greedy or DP which do not handle pairwise ordering correctly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Custom comparator sorting is the standard solution for this problem [OK]

Hint: Compare concatenations as strings to decide order [OK]

Common Mistakes:

• Assuming greedy pick of largest integer works
• Using DP which is unnecessary
• Brute force is correct but inefficient

2. You are given a sequence of integers and need to find the length of the longest subsequence where the differences between successive elements strictly alternate between positive and negative. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Dynamic Programming with a 2D table tracking subsequence lengths for each index and difference sign

B. Brute force recursion exploring all subsequences and checking alternating differences

C. Greedy approach tracking the direction of the last difference and counting peaks and valleys

D. Sliding window approach maintaining a contiguous alternating difference substring

Solution

1. Step 1: Understand problem constraints

   The problem requires the longest subsequence with alternating positive and negative differences, not necessarily contiguous.

2. Step 2: Identify optimal approach

   Dynamic programming is possible but less efficient; brute force is exponential; sliding window fails because subsequence need not be contiguous. The greedy approach tracking last difference direction and counting peaks and valleys achieves O(n) time and O(1) space optimally.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Greedy with direction tracking matches problem requirements [OK]

Hint: Longest alternating difference subsequence -> greedy direction tracking

Common Mistakes:

• Confusing subsequence with substring
• Assuming DP is always needed
• Trying brute force without pruning

3. Consider the following buggy code for the Gas Station problem. Which line contains the subtle bug that can cause incorrect results?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    # Bug: missing total gas check
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

medium

A. Line 3: net array computation

B. Line 4: missing total gas vs total cost check

C. Line 6: prefix sums computation loop

D. Line 8: checking prefix sums for valid start

Solution

1. Step 1: Identify missing total gas check

   The code does not check if sum(net) < 0 before proceeding, which can cause incorrect start index or false positives.

2. Step 2: Verify other lines

   Net array, prefix sums, and prefix difference checks are correct and standard.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing total gas check leads to incorrect results [OK]

Hint: Always check total gas >= total cost before searching start [OK]

Common Mistakes:

• Forgetting total gas check
• Misusing modulo in prefix sums
• Resetting start without resetting tank

4. What is the worst-case time complexity of the BFS-based solution for Jump Game II on an input array of length n?

medium

A. O(n^2)

B. O(n)

C. O(n log n)

D. O(n^3)

Solution

1. Step 1: Identify outer and inner loops

   The BFS processes each index once, but for each index, it may enqueue up to nums[pos] next positions, which can be up to n.

2. Step 2: Analyze nested iteration

   In worst case (e.g., nums[i] = n for all i), inner loop runs O(n) times for each of O(n) indices -> O(n^2) total.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops over n indices and jumps -> O(n^2) [OK]

Hint: Nested loops over n indices and jumps -> O(n^2) [OK]

Common Mistakes:

• Assuming BFS is always O(n)
• Confusing with greedy linear time
• Ignoring inner loop over jump range

5. What is the time complexity of the optimal greedy algorithm using a stack to remove k digits from a number string of length n to get the smallest number?

medium

A. O(n) because each digit is pushed and popped at most once

B. O(n^2) because nested loops are needed to find digits to remove

C. O(n log n) due to sorting digits internally

D. O(n * k) because each digit can cause up to k pops

Solution

1. Step 1: Identify operations per digit

   Each digit is pushed onto the stack once and can be popped at most once when a smaller digit arrives.

2. Step 2: Analyze total operations

   Since each push and pop happens at most once per digit, total operations are proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Stack operations are linear in n, no nested loops [OK]

Hint: Each digit pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Assuming worst case k pops per digit -> O(n*k)
• Confusing with sorting complexity
• Thinking nested loops are needed