If you are a newcomer or a don’t-know-anything about Computer Science and Algorithms, let me know what you’d think of Greedy Algorithm 🥹
If I were to introduce my friends to Computer Science, I would introduce the Greedy Algorithm to them first and foremost, right after “Hello World” because of how fun it is.
You can just think of this Greedy Algorithm as some puzzles you have solved in Middle School or Elementary School even. It’s tricky, can be a bit difficult, but using coding to solve them can be so fun.
As a matter of fact, this is ChatGPT’s answer to my prompt: “Explain Greedy Algorithm for me like I’m a 3-year-old.”
“Imagine you have a big box of toys, and you want to grab as many as you can, really fast! So, you keep picking the biggest toy you can see each time, filling your arms as much as you can. This way, you get a lot of toys quickly, even though you might not pick the best ones if you thought about it longer. That’s like the greedy algorithm: it keeps choosing the biggest or best thing right away, without thinking about all the choices first.”
Take a look at one of the Easy problem with Greedy as its tag, the 605. Can Place Flowers: https://leetcode.com/problems/can-place-flowers/description/
“You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.
Given an integer array flowerbed containing 0's and 1's, where 0means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.”
Here’s the example:
Input: flowerbed = [1,0,0,0,1], n = 1
Output: true
Input: flowerbed = [1,0,0,0,1], n = 2
Output: falseI just think it’s such a fun brainteaser.
Just by looking at the example, you can figure out right away which is a good position and which is not, right?
However, translating this into code or teaching a machine where to plant a flower (or not) can be slightly more complex for beginners or those unfamiliar with coding. Considerations include:
- What if no pots are available for planting flowers?
- What if there are only two pots?
- How do you handle multiple pots? How do you count, and how do you make the machine count?
The beauty of the greedy algorithm lies in its simplicity; often, thinking less leads to better solutions. Here’s a straightforward implementation for the flower planting problem:
class Solution
{
public boolean canPlaceFlowers(int[] flowerbed, int n)
{
if (n == 0) {
return true;
}
for (int i = 0; i < flowerbed.length; i++) {
if (flowerbed[i] == 0 &&
(i == flowerbed.length - 1 || flowerbed[i + 1] == 0) &&
(i == 0 || flowerbed[i - 1] == 0)) {
n--;
if (n == 0) {
return true;
}
flowerbed[i] = 1;
}
}
return false;
}
}In this solution, I checked if any pots were available, whether the first pot was not planted among other conditions through traversing through the “garden.”
It’s like pointing at each plant from left to right, figuring out whether this pot has “friends” next to it.
This approach may seem a bit brute-force, but it’s incredibly accessible for a Computer Science algorithm, especially for an easy-level problem.
Okay, but this is an easy-level type of question, right? What about Greedy Algorithm in Medium level?
For a Medium, I would like to introduce an interesting problem: 781. Rabbits in Forest: https://leetcode.com/problems/rabbits-in-forest/description/
Here’s the problem:
“There is a forest with an unknown number of rabbits. We asked n rabbits “How many rabbits have the same color as you?” and collected the answers in an integer array
answerswhereanswers[i]is the answer of theithrabbit.Given the array
answers, return the minimum number of rabbits that could be in the forest.”
And here it introduces the concept of HashMaps or Dictionaries in a practical context :) Quite convenient, right?
class Solution
{
public int numRabbits(int[] answers)
{
HashMap<Integer, Integer> coloredRabbits = new HashMap<>();
int rabbits = 0;
for (int ans : answers) {
if (ans == 0) {
rabbits++;
}
else {
if (coloredRabbits.containsKey(ans)) {
if (coloredRabbits.get(ans) <= ans) {
coloredRabbits.put(ans, coloredRabbits.get(ans) + 1);
}
else {
rabbits = rabbits + ans + 1;
coloredRabbits.put(ans, 1);
}
}
else {
rabbits = rabbits + ans + 1;
coloredRabbits.put(ans, 1);
}
}
}
return rabbits;
}
}Imagine you’re in a forest, and you encounter several groups of rabbits. Each rabbit tells you how many other rabbits have the same color as itself. Your task is to figure out the minimum number of rabbits in the forest.
We use a HashMap, you can think of it like a Dictionary that has a keyword and a definition, to keep track of the groups and how many rabbits we’ve counted in each one.
This also resembles the way anyone would count something different right? Make a table of the categories and the count each time you found a new one!
Here’s how the solution works, step by step:
- Initialize a Counter: We start with a count of zero rabbits.
- Iterate Through Answers: For each rabbit, we look at the number it gives (let’s call it
ans). - Solo Rabbits: If a rabbit says
0, it means there are no other rabbits of its color, so it's alone. We simply add one to our total rabbit count. - Grouped Rabbits: If a rabbit gives a number other than
0, this indicates it's part of a group with the same color.
- If we’ve already encountered rabbits claiming to have the same number of color-mates (
ans), we update our count of that group. - If the group reaches the size the rabbit mentioned (
ans), any additional rabbits of the same color will start a new group. - If this is the first time we’re hearing
ans, we assume there's a full group ofans + 1rabbits (including the one we're talking to) and add that to our total count.
The key in the HashMap is the number of other rabbits each rabbit claims to have of the same color (the ans), and the value is how many rabbits we've encountered with that same answer.
By iterating through all the answers and applying this logic, we ensure that we count the minimum number of rabbits that could be in the forest, accounting for all the groups and solo rabbits we encounter.
In essence, this approach allows us to build a picture of the rabbit population in the forest, ensuring we count all individuals while accounting for the groups they form based on their color.
Finally, let’s go to the problem in which made me realize how little I know about Greedy Algorithm :) the Question 3 in the Leetcode Contest on April 6th, also known as, 3107. Minimum Operations to Make Median of Array Equal to k: https://leetcode.com/problems/minimum-operations-to-make-median-of-array-equal-to-k/description/
Firstly, here was how I solved the problem at first:
The first code snippet uses a brute-force approach to adjust the array’s elements until the median equals k:
class Solution
{
public long minOperationsToMakeMedianK(int[] nums, int k)
{
Arrays.sort(nums);
int count = 0;
while (true) {
int median = nums[nums.length / 2];
if (median == k) {
break;
}
if (median < k) {
for (int i = nums.length / 2; i < nums.length; i++) {
if (nums[i] < k) {
nums[i]++;
count++;
break;
}
}
}
else {
for (int i = nums.length / 2; i >= 0; i--) {
if (nums[i] > k) {
nums[i]--;
count++;
break;
}
}
}
Arrays.sort(nums);
}
return count;
}
}To a non-programmer, it might not be evident that this solution suffers from a Time Limit Exceeded (TLE) error.
First approach breakdown:
- Time Complexity: This method is inefficient, especially for large arrays, because it sorts the array multiple times within a loop.
- Time Limit Exceeded (TLE): Due to its inefficiency, it exceeds the time limit for large test cases.
Consequently, I discovered a more efficient, greedy method in the solution section:
class Solution
{
public long minOperationsToMakeMedianK(int[] nums, int k)
{
int n = nums.length;
long res = 0;
Arrays.sort(nums);
for (int i = 0; i <= n / 2; ++i) {
res += Math.max(0, nums[i] - k);
}
for (int i = n / 2; i < n; ++i) {
res += Math.max(0, k - nums[i]);
}
return res;
}
}Second approach breakdown:
- Sorting: The array is sorted once at the beginning, reducing the overall time complexity.
- Efficiency: Instead of adjusting one element at a time, it calculates the total number of operations needed for each half of the array to meet the median requirement, resulting in a much faster solution.
- Optimization: This method is more direct and does not repeatedly sort the array, unlike the first approach. It computes the total adjustments needed for the array’s elements to ensure the median equals
kin a single pass through the array.
That was the Greedy Algorithm breaking down and what I have learnt so far. If you are interested in practicing for it, here’s a list of problems from Leetcode that could be beneficial:
Easy:
- https://leetcode.com/problems/assign-cookies/
- https://leetcode.com/problems/array-partition/
- https://leetcode.com/problems/lemonade-change/description/
Medium:
- https://leetcode.com/problems/boats-to-save-people/description/
- https://leetcode.com/problems/bag-of-tokens/description/
- https://leetcode.com/problems/pancake-sorting/description/
In wrapping up, the Greedy Algorithm isn’t just a smart way to solve problems in Computer Science; it’s a friendly gateway into the world of programming, especially for those new to the field.
If you have a friend of different major, asking about algorithms and data structures, what would be your first suggestions? 🙈
Thanks for reading and have fun coding! 🤓
