Theoretical Basics of Greedy Algorithms

By choosing the local optimum at every stage, we aim to achieve the global optimum. The key to selecting a greedy algorithm is: it’s possible to deduce the global optimum from the local optimum.

How to verify if you can use greedy:

1. Provide a counterexample: If you can’t think of a counterexample, try harder.
2. Mathematical induction.

Steps for a greedy algorithm:

1. Decompose the problem into several sub-problems.
2. Identify an appropriate greedy strategy.
3. Find the optimal solution for each sub-problem.
4. Stack the local optimums to form a global optimum.

Example: Leetcode 455: Distributing Cookies

• Local Optimum: Give the largest cookie to the child with the biggest appetite.

• Global Optimum: Feed as many children as possible.

class Solution:
    def sort(self, nums):
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if nums[j] < nums[i]:
                    temp = nums[i]
                    nums[i] = nums[j]
                    nums[j] = temp
    
    def findContentChildren(self, g, s):
        self.sort(g)
        self.sort(s)
        count = 0
        i = 0  # pointer to g
        j = 0  # pointer to s
        
        while i < len(g) and j < len(s):
            if s[j] - g[i] >= 0:
                count += 1
                i += 1
                j += 1
            else:
                j += 1
        
        return count

Example: Leetcode 376 Swing Sequence

This question is divided into three situations:

1. there are flat slopes in the upper and lower slopes;
2. only the first and last elements;
3. monotonic slopes in which there are flat slopes; (prediff just records the direction of the initial slope when the swing appears)
   Assume that the rightmost side has a slope, so the initial RESULT = 1.

   class Solution:
       def wiggleMaxLength(self, nums):
           # only one element
           if len(nums) == 1:
               return 1
           
           # three conditions: Up and down with flat slopes; first element; monotone with flat slopes
           result = 1
           prediff = 0  # This is equivalent to adding another element at the beginning of the array with the same value as its first element.
           curdiff = 0
           
           for i in range(len(nums) - 1):
               curdiff = nums[i + 1] - nums[i]
               if (prediff <= 0 and curdiff > 0) or (prediff >= 0 and curdiff < 0):
                   result += 1  # Satisfies the need for a flat slope up and down
                   # Dealing with monotony with flat slopes
                   prediff = curdiff
           
           return result

   Example: Leetcode 53 Maximum Subarray Sum

   If successive sums are negative, they are immediately discarded and the next number is chosen as the starting position,using greedy algorithm:

   class Solution:
       def maxSubArray(self, nums):
           result = -1000000  # Set result to a very small value
           count = 0  # Record the current traversed value
           
           for i in range(len(nums)):
               count += nums[i]
               
               if count > result:
                   result = count
               
               if count < 0:
                   count = 0  # Reset count to start accumulating from the next position, reflecting the greedy approach
           
           return result

Example: Leetcode 860 Lemonade To Find Change

Greedy thought: leave as many 5’s as possible because 5’s are more versatile and can make change not only to 20 but also to 10, whereas 10 can only make change to 20.

class Solution:
    def lemonadeChange(self, bills):
        five = 0
        ten = 0
        twenty = 0
        
        for i in range(len(bills)):
            if bills[i] == 5:
                five += 1
            if bills[i] == 10:
                if five == 0:
                    return False
                else:
                    five -= 1
                    ten += 1
            if bills[i] == 20:
                if ten > 0 and five > 0:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        
        return True