Candy

To distribute the candies according to the given requirements, we need to make sure that we give at least one candy to every child and more candies to children with higher ratings compared to their neighbors. This problem can be solved in two passes.

Here’s a step-by-step explanation:

Initialize Candies Array: Create an array candies of the same length as ratings, and initialize all elements to 1, as every child must have at least one candy.
Forward Pass: Iterate from left to right through the ratings array. If a child has a higher rating than the child on the left, set candies[i] = candies[i-1] + 1.
Backward Pass: Iterate from right to left through the ratings array. If a child has a higher rating than the child on the right and candies[i] is less or equal to candies[i+1], set candies[i] = candies[i+1] + 1.
Calculate Total Candies: Sum the values in the candies array.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n

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

        # Backward pass
        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)

The time complexity of this solution is O(n), and the space complexity is also O(n), where n is the length of the ratings array. This code ensures that the candies are distributed according to the given rules and returns the minimum number of candies required.

Identifying Problem Isomorphism

“Candy” (LeetCode #135) can be approximately mapped to “Trapping Rain Water” (LeetCode #42).

Reasoning:

In “Candy”, the amount of candy each child gets depends on their rating and the rating of their neighbors. Specifically, each child should have at least one candy, each child with a higher rating than their neighbor should get more candies than their neighbor, and the minimum total number of candies should be used.

In “Trapping Rain Water”, the amount of water each position can trap depends on its height and the height of its neighbors. Specifically, a position can trap water if its height is less than the height of its neighbors, and the volume of water trapped is the minimum of the maximum height of its two neighbors minus its own height.

Here’s the approximate mapping: For each child in the “Candy” problem, there corresponds the same position in the height array for the “Trapping Rain Water” problem. The child’s rating maps to the height of the position, and the amount of candy the child gets maps to the volume of water the position can trap.

This mapping is approximate. The two problems have similar structure in terms of considering a position and its neighbors to decide the value of the position (candy or water), but the condition for assigning the value differs. In “Candy”, the value depends on the comparison of the child’s rating with its neighbors, while in “Trapping Rain Water”, the value depends on the minimum of the maximum height of its neighbors minus its own height.

So, while the two problems do not map exactly in terms of their conditions, they do map approximately in terms of their structure: both require you to consider a position and its neighbors to decide the value of the position.

10 Prerequisite LeetCode Problems

To prepare for the “135. Candy” problem, understand concepts like greedy algorithms and array manipulations. Here are 10 problems to build up to it:

“121. Best Time to Buy and Sell Stock”: This problem helps in understanding the profit/loss concept that can be solved with a simple iteration.
“122. Best Time to Buy and Sell Stock II”: This problem introduces the concept of multiple transactions, paving the way for a better understanding of greedy algorithms.
“455. Assign Cookies”: This problem is an application of the greedy algorithm, where you’re trying to maximize the number of content children.
“605. Can Place Flowers”: This problem deals with determining if n new elements can be placed in certain positions of an array based on some rules.
“392. Is Subsequence”: This problem also uses greedy algorithm concepts, checking whether one sequence can be found within another.
“621. Task Scheduler”: This problem involves scheduling and interval allocation, similar to the candy problem.
“860. Lemonade Change”: This problem requires making optimal decisions at every step to give change, an example of a greedy problem.
“1221. Split a String in Balanced Strings”: This is an easy problem to understand the concept of maintaining balance between two characters/elements.
“1351. Count Negative Numbers in a Sorted Matrix”: Helps to practice working with 2D arrays, although not directly related, it is good for array manipulation.
“1710. Maximum Units on a Truck”: This is another problem based on the greedy algorithm, and focuses on optimizing a certain parameter.

These problems have a simpler complexity than “135. Candy” and they gradually introduce concepts that are crucial in solving it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def candy(self, ratings: List[int]) -> int:
        n=len(ratings)
        temp = [1]*n

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

        for i in range(n-2,-1,-1):
            if(ratings[i]>ratings[i+1] and temp[i]<=temp[i+1]):
                temp[i]=temp[i+1]+1

        return sum(temp)

Candy - The problem involves distributing candies among children following certain rules. It’s about allocating things according to rules, so it’s an Allocation Problem.

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2] Output: 5 Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively. Example 2:

Input: ratings = [1,2,2] Output: 4 Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

n == ratings.length 1 <= n <= 2 * 104 0 <= ratings[i] <= 2 * 104

Language Agnostic Coding Drills

Lists and List comprehension:
- Create lists, add elements to a list, access list elements and modify them.
- Use list comprehensions to generate a new list from an existing one.
For Loops:
Drills:
- Write a for loop to iterate over a list or a range of numbers.
- Understand the usage of loop variables and how to use them to access list elements.
If-Else Statements:
Drills:
- Write if-else conditions and understand how they control the flow of the program.
- Combine multiple conditions using logical operators like and, or.
Working with Indices in Lists:
Drills:
- Understand the concept of index in a list, how they start from 0 and go up to n-1 where n is the size of the list.
- Learn how to use indices to access list elements, compare elements at different indices, etc.
Basic Arithmetic Operations:
Drills:
- Add, subtract, multiply, and divide integers.
- Use of incrementing +=.
Usage of built-in Python functions: len() and sum():
Drills:
- Find the length of a list using len().
- Calculate the sum of elements in a list using sum().

In this code, a greedy algorithm approach is used to solve the problem.

First, a list of length n is created, filled with 1s, indicating that each child gets at least one candy.
Then, a left-to-right pass is made through the list of ratings. If the current child’s rating is higher than the previous child’s, then the current child gets one more candy than the previous child.
Then, a right-to-left pass is made. If the current child’s rating is higher than the next child’s and the current child’s current candy count is less or equal to the next child’s, then the current child gets one more candy than the next child.
Finally, the total number of candies distributed is calculated by summing up the numbers in the temp list.

Targeted Drills in Python

Lists and List comprehension:
- Create a list of first 10 natural numbers.
  1 2
  numbers = [i for i in range(1, 11)] print(numbers)
- Create a new list which contains squares of all numbers from the previously created list.
  1 2
  squares = [n**2 for n in numbers] print(squares)

For Loops:

Write a for loop to iterate over the list and print each number.
1 2
for num in numbers: print(num)

Use the loop variable to access elements of the list and find their sum.

1
2
3
4
sum_of_numbers = 0
for num in numbers:
    sum_of_numbers += num
print(sum_of_numbers)

If-Else Statements:

Write a program that prints whether each number in the list is even or odd.

1
2
3
4
5
for num in numbers:
    if num % 2 == 0:
        print(f"{num} is even")
    else:
        print(f"{num} is odd")

Working with Indices in Lists:

Print elements at even indices in the list.

1
2
3
for i in range(len(numbers)):
    if i % 2 == 0:
        print(numbers[i])

Basic Arithmetic Operations:
- Calculate and print the average of numbers in the list.
  1 2
  average = sum(numbers) / len(numbers) print(average)
Usage of built-in Python functions: len() and sum():
- Use len() to get the number of elements in the list.
  1 2
  length = len(numbers) print(length)
- Use sum() to get the sum of all numbers in the list.
  1 2
  total = sum(numbers) print(total)