I've seen there are many amazing tutorials and problem lists out there for various Concepts like Dynamic Programming by @aatalyk. I plan on compiling one for Greedy in C++ so that it's helpful for me as well as people starting their interview preps. Java and Python solution can be found in the solution column of the questions. It's incomplete but feel free to suggest some resources which can benefit people while revising Greedy.
Some Background
Greedy algorithm is nothing but a paradigm which builds problems piece by piece. In recursion, we keep on dividing a big problem into multiple smaller chunks and solving those sub problems which is finally used to solve our actual problem. But this isn't the case for Greedy. In this, at any instant, we choose a piece of solution which will offer the most obvious and immediate benefit. For example the famous problem Fractional Knapsack. We keep on choosing the items which are local maximathat is, the items which have maximum value of "profit per unit weight" and in the end get the global maximum.
Some popular Greedy Algorithms
- Dijkstra’s Shortest Path
- Kruskal’s Minimum Spanning Tree (MST)
- Prim's Minimum Spanning tree
- Huffman Coding
Problem List for Greedy
These problems are sufficient for developing intuition for Greedy.
When to use it ?
Whenever we see optimum or maximum or minimum or larget or smallest, the first approach which should strike our mind should be Greedy or Dynamic Programming. If the problem is solvable via recursion, one should do for memoized recursion or DP else start with the brute force and reduce it to Greedy.
Some problems based on Greedy for beginners with the intuition behind solving them:
Max-Consecutive-Ones
Problem Statement In an array of 0s and 1s, we are to fing length of the longest chain of 1s.
Intuition Traverse the whole array once and find lengths of various chains of 1. Finally return the length of the longest chain.
Code
int count = 0 , count_max = 0;
for(auto& num : nums)
{
if(num == 1)
++count;
else
{
count_max = (count_max < count) ? count : count_max;
count = 0;
}
}
return (count > count_max) ? count : count_max ;Best time to buy and sell stocks
Problem Statement Given array of prices, you can buy stock and sell it on a later date only once. Goal is to maximize profit.
Intuition The brute for solution would be finding all such possibilities of profit but the time complexity shoots to O(n^2) so this is rejected because it's possible to do it in O(n) time. Simply keep track of the local minima at each step and which traversing the array, find the difference between array element and local minima and return the max difference.
Code
int max_profit = 0, min_price = INT_MAX;
for(int i = 0 ; i < prices.size() ; ++i )
{
min_price = (min_price > prices[i]) ? prices[i] : min_price ;
max_profit = (max_profit < prices[i] - min_price) ? prices[i] - min_price : max_profit;
}
return max_profit ; Jump Game
Problem Statement Given an array of non-negative integers nums, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.
Intuition We need to determine the farthest_index that can be reached while traversing the array. If the farthest_index is greater than or equal to the last index, we should return true else false. The time complexity will be O(N) and space complexity O(1).
Code
bool canJump(vector<int>& nums) {
int n = nums.size(), farthest_index = 0 ;
for(int i=0; i<n; i++) {
if(farthest_index < i) return false;
farthest_index = max (i + nums[i] , farthest_index) ;
}
return true;
}Jump Game II
Problem Statement Given an array of non-negative integers nums, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. You can assume that you can always reach the last index.
Intuition As soon as we see the word minimum number of steps, our aim should be to maximize our reach at every step thus giving the greedy solution of O(N) time. As soon as the right index where we reach is greater than or equal to our last index, we can safely return the step number.
Code
int jump(vector<int>& nums) {
int step = 0;
for(int l = 0, r = 0; r < nums.size() - 1; step++){
int r_new = 0;
for(int i = l; i <= r; i++) r_new = max(r_new, i + nums[i]);
l = r + 1;
r = r_new;
}
return step;
}Gas Station
Problem Statement Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.
Intuition The starting index would be such that gas[index] >= cost[index] at that particular index. Idea is to go to stations from which we can travel to the farthest so that you can travel the farthest.
Code
int n = cost.size();
int sum;
for(int i=0; i<n; ++i) {
if(gas[i] < cost[i]) continue; //idea starting index should've gas[i] >= cost[i]
int j = 0, k, sum = 0;
for(j=0 ; j < n ; ++j){
k = (i+ j) % n;
sum += gas[k] - cost[k];
if (sum < 0) {
if(k<i)
return -1;
else
i = k;
break;
}
}
if(j==n) return i;
}
return -1;Lemonade Change
Problem Statement Return true if and only if you can provide every customer with correct change.
Intuition You need to keep the track of the amount of change you have. Customer gives 5 then no problem. If customer gives 10 then you should have 5 bills you have and increment 20, first you try to give 5. If you don't have 5 but if you don't have it, return false.
Code
int n5 = 0 , n10 = 0 ;
int n= bills.size();
for(int i=0; i<n; i++)
{
if (bills[i] == 5) ++n5;
else if(bills[i] == 10 )
{
if(n5) {
--n5;
++n10;
}
else return false;
}
else
{
if(n10 && n5)
{
--n10;
--n5;
}
else
{
if(n5>=3)
{
n5-=3;
}
else return false;
}
}
}
return true;Some amazing General Discussions