Greedy Algorithm
Summary
The greedy algorithm always choose locally optimal solution at each step with the hope of finding a global optimum.
Sorting + Iteration
Idea: When we have limited resources (e.g., time, space, cookies, etc), we can sort the resources and the need and try to use them in order.
Assign Cookies (Leetcode 455)
This is a bit similar to two pointers. The key constraint is that each child can take one cookie at most. This means, we can sort children and cookies by their sizes and try to assign cookies to children in order.
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
id_child = 0
id_cookie = 0
while id_child < len(g) and id_cookie < len(s):
if s[id_cookie] >= g[id_child]:
id_child += 1
id_cookie += 1
return id_child
Non-overlapping Intervals (Leetcode 435)
Sort by end time and then check if the next interval starts after the previous interval ends.
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1])
n_remv, pre_end = 0, intervals[0][1]
for i in range(1, len(intervals)):
if pre_end > intervals[i][0]:
n_remv += 1
else:
pre_end = intervals[i][1]
return n_remv
Minimum Number of Arrows to Burst Balloons (Leetcode 452)
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
points.sort(key=lambda x: x[1])
arrows = 1
current_end = points[0][1]
for i in range(1, len(points)):
if points[i][0] <= current_end:
continue
else:
arrows += 1
current_end = points[i][1]
return arrows
Min-Max/Max-Min
Idea: Alternating between min and max.
Candy (Leetcode 135)
Idea: 1) left to right, 2) right to left. The problem can then be solved
class Solution:
def candy(self, ratings: List[int]) -> int:
n_child = len(ratings)
candy = [1] * n_child
for i in range(1, n_child):
if ratings[i] > ratings[i-1]:
candy[i] = candy[i-1] + 1
for j in range(n_child-1, 0, -1):
if ratings[j-1] > ratings[j]:
candy[j-1] = max(candy[j-1], candy[j]+1)
return sum(candy)
Can Place Flowers (Leetcode 605)
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
if n == 0:
return True
prev_flower = 0
n_flower = 0
for i in range(len(flowerbed)):
if flowerbed[i] != 0:
continue
is_left_empty = (i == 0) or (flowerbed[i - 1] == 0)
is_right_empty = (i == len(flowerbed) - 1) or (flowerbed[i + 1] == 0)
if is_left_empty and is_right_empty:
flowerbed[i] = 1
n_flower += 1
if n_flower >= n:
return True
return False
Interval / Jump
Idea: Each step, we can try its best to jump to the farthest index.
Jumping Game I (Leetcode 55)
Idea: for each element, check how much it can push the current farthest index. This eventually leads to the final answer.
class Solution:
def canJump(self, nums: List[int]) -> bool:
farthest = 0
n = len(nums)
for i in range(n-1):
farthest = max(farthest, i + nums[i])
if farthest <= i:
return False
return farthest >= n-1
Jumping Game II (Leetcode 45)
Idea: Maintain a search range [left, right] of the farthest index that can be reached and update it at each step.