Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article at OpenGenus, we will discuss the about how to master greedy algorithms by solving 7 basic problems using greedy algorithmic ideas.
TABLE OF CONTENT
- Valid Palindrome2
- Queue Reconstruction By Height
- Shortest unSorted Continous Subarray
- Dota 2 Senate
- Valid Paranthesis String
- Can Place Flowers
- patching Array
- Other Applications of greedy
Problem 1: Valid Palindrome II
Statement : We have been given a string and we have to delete single character from it to make string palindrome.
Return true, if it is possible to make palindrome otherwise false.
Example 1
Input: s = "bbaabbc"
Output: true
Explanation: You can delete the character 'c'.
Solution
Approach
We have used two pointer+greedy technique here. Initially i is at 0 and j is at last index n-1.
Explanation
- We need to make string palindrome somehow by deleting atmost one character. We are using two pointer technique where our i initially is pointing at zero index and j at last index. If our element at the first and last element equal. we will do nothing and simply increment and decrement our pointers but at any point our element at i and j becomes not equal then we delete the character at i and check if its a palindrome , if its palindrome we will return true, if not we will delete char at j and checks if its palindrome, if its palindrome we will return true.
- If both conditions turns out to be false then we will return false.
- After Deleting atmost character for checking if string is palindrome , we have made function ispal as shown in code.
Dry Run
- The initial string is "abc".
- validPalindrome function is called: i = 0, j = 2
- s[i] = 'a', s[j] = 'c': Mismatch found.
- Two modified strings, str1 and str2, are created:
- str1 = "abc" (Removing character at index i = 0)
- str2 = "abc" (Removing character at index j = 2)
- Check if any of the modified strings (str1 or str2) are palindromes:
- IsPal("ab"): This is not a palindrome.
- IsPal("bc"): This is not a palindrome.
bool ispal(string a) {
for(int i=0 , j=a.size()-1 ; i<j ;i++ , j--) {
if(a[i]!=a[j]) return false;
}
return true;
}
bool validPalindrome(string s) {
for(int i=0,j=s.size()-1;i<j; i++ ,j--) {
if(s[i]!=s[j]) {
string a=s,b=s;
return ispal(a.erase(i,1)) || ispal(b.erase(j,1));
}
}
return true;
}
Complexity
- time complexity:
Θ(n) - Space complexity:
Θ(1)
Problem 2: Queue Reconstruction By height
Statement: In this Question we have been given person represent by index 0 and we have been given number of person greator than current person present before them.
For example In the following example lets take [6,1] here 1 person greator than 6 present before 6.[5,2] 2 persons greater than 5 present before 5.
We have to arrange array in such way such that we will satisfy all these conditions.
Example 1
Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Solution
Explanation
- Core Idea Behind this Solution is Sorting. Now You may think Why Sorting? So this is why , We Know that it is given in our question we need to place elements in such a way that [a,b] - If there are b elements which are greator than a they must be present before a.
- Now Just think about it you are current element with value 6 and there is only one element which is greator than you than that greator element must be place before current element. So for this we are sorting in decreasing order.
- We will sort in decreasing order because we want greator element always on the left side of current element.
- Now Approach is to simply sort the array in decreasing order and then make a ans vector where we will be inserting elements in the ans vector based on the index we encounter for example sorted array is [7,0], [5,0]
- Here In Answer vector firstly we will insert 7 at index 0 then We Will Insert 5 at index 0, 5 will override 7. Now you may think why?
- Why we are using because we know that we always want greator element on the left than current element. So Here 5 will be placed before 7 then it will not create any issue as 5 is lesser than 7 so it satisfies the condition that there are 0 elements greator than 7 before 7. But If We Place 5 after 7 then we donot satisfies the condition that there are 0 elements greator than 5 placed before 5.
Approach
-
Sort By Decreasing Order
-
[7,0][7,1][6,1][5,0][5,2][4,4]
-
Iterating through the sorted array and inserting each person at the index specified by their p[1] value into the ans array
-
ans.insert(ans.begin() + k, p) inserts the current p into the ans vector at position k.
-
[7, 0]: Insert at index 0. ans = [[7, 0]]
[7, 1]: Insert at index 1. ans = [[7, 0], [7, 1]]
[6, 1]: Insert at index 1. ans = [[7, 0], [6, 1], [7, 1]]
[5, 0]: Insert at index 0. ans = [[5, 0], [7, 0], [6, 1], [7, 1]]
[5, 2]: Insert at index 2. ans = [[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]]
[4, 4]: Insert at index 4. ans = [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]] -
The final output after insertion based on the order specified by the people array would be: [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]].
static bool cmp(vector<int>&a ,vector<int>&b) {
if(a[0]==b[0]) {
return a[1]<b[1];
}
return a[0]>b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(),people.end(),cmp);
vector<vector<int>> ans;
for(auto m: people)
{
ans.insert(ans.begin()+m[1],m);
}
return ans;
}
Complexity
- Time complexity:
Θ(n) - Space complexity:
Θ(1)
Problem 3: Shortest-Unsorted-Continous-Subarray
Statement : In this Question We need to find the subarray. Subarray is continous sequence of array, we need to find subarray in such a way that if we sort that subarray , entire array got sorted In the following example
Example 1
Input: nums = [1,3,4,7,6,8,9]
Output: 5
Explanation: So here You need to sort the subarray [7,6,8] to make entire array get sorted.
Solution
Explanation
- We will create another vector or array and copy then another vector with given original vector and sort the another vector
- Then We Will loop till the size of array or vector and checks if the current element in the another vector is equal to the element in the original vector.
- If they are equal it means they are already sorted and correct.
- At any moment the current element in the another vector becomes not equal to the element in the original vector then it means we need to sort this element so we will store the index of it in start variable and similarly we will store the last element index which is not equal with original vector
- At end, we will print the length - end-start+1 that we need to sort.
Approach
We will simply create an array and copy the array temp array with original array and will sort temp and will search for index where any element of original array is not equal to temporary array.
int findUnsortedSubarray(vector<int>& nums) {
vector<int> ans = nums;
sort(ans.begin(), ans.end());
int start = -1, end = -1;
for (int i = 0; i < ans.size(); i++) {
if (ans[i] != nums[i]) {
if (start == -1) {
start = i;
}
end = i;
}
}
return (start == -1) ? 0 : end - start + 1;
}
Complexity
- Time complexity:
Θ(nlogn) - Space complexity:
Θ(1)
Problem 4: Dota 2 Senate
Statement:
In this Question we have two parties both parties are opposing,Both parties are playing a game with FIFO , We have been given an array where we have radiant and dire. If in the array Radiant is present first Radiant has power to ban all the rights of dire. similary if dire is present first dire has power to ban radiant.
At the end, we have to find out whose all rights get banned, whose all rights get banned that person will be lost and party which left wins.
Example 1
Input: senate = "RD"
Output: "Radiant"
Explanation:
Here in round 1 - radiant take turn and ban dire 2
hence radiant wins.
example2
RDRDD
Here first radiant at index 0 bans dire at index 1, radiant at index 2 bans dire at index 3, dire at last index ban first radiant index 0. Now radiant at index 2 is still alive.
Solution
Explanation
- Idea behind this approch is FIFO. If Radiant Will encounter First In the Array then radiant will ban dire rights otherwise Dire will ban radiant rights.
- We are placing all radiant index in one queue and all dire index in one queue.
- So What We are Doing if We encounter Radiant first then for banning next dire we pop that dire from queue.
- Similarly If Dire index is less than it means Dire comes first it can ban Radiant. So we will pop radiant index from queue.
- At end whoever remains in queue either Dire or Radiant, that will win
- Understand through this queue 1 has index 2,4 and queue 2 has index 1,3
- Queue 1 Representing all the indexed of Radiant and Queue 2 representing all the indexes of dire
- So We will take out index 2 of radiant and index 1 of Dire, Here index 1 of dire is smaller so dire wins we will push dire index back to queue and radiant will remain popped
- queue 1= [4]
- queue 2=[3,1]
- Now we will take out 4 of Radiant and index 3 of Dire . Again Dire has less index Dire wins.
- queue 1=[]
- queue2 =[3,1]
- so queue 1 becomes empty and dire still has elements in queue so DIRE WINS.
Approach
- As mentioned in question, if radiant is taking turn then radiant will ban dire rights
- Here are all the cases where radiant can won- R, RD , RDRDD , RDDR, DRR and many more
- Here are all the case where dire can won- DR, D , DRDRR , DRRD , DDRRR
- We are solving this question By using two queue
- Steps of Algorithm
- Create Two Queue. Push the index of radiant in the rq and dire in the dq
- Here we are using queue because we want FIFO. We know that if radiant comes first in the array then radiant will ban dire and remains in the array
- We will pop front elements of rq and dq into a and b variables and pop them
- we will check whose index is less. if a value is less thenj we will again push our a in rq else push b in dq
- At the end which queue has greator size or which element is present wins.
string predictPartyVictory(string senate) {
queue<int> rq, dq;
for(int i=0; i<senate.size(); i++)
senate[i] == 'R' ? rq.push(i): dq.push(i);
int a, b;
while(!rq.empty() and !dq.empty()){
a = rq.front(), b = dq.front();
rq.pop(), dq.pop();
if (a < b)
rq.push(a+senate.size());
else
dq.push(b+senate.size());
}
if (rq.size() > dq.size())
return "Radiant";
else
return "Dire";
}
Complexity
- Time complexity:
Θ(n) - Space complexity:
Θ(n)
Problem 5: Valid Paranthesis String
Statement:
A paranthesis is valid -
- '*' if we encounter * , * also means open bracket
- ( this also means open bracket
- ) means close bracket
- '*' also means close bracket
At last all open bracket must have closed brackets to make string valid paranthesis string.
Example 1
Input: s = "(*))"
Output: true
Solution
Explanation
- How we can solve this Question just think about it? Greedy Involves alot of calculations and making up a formulae that could solve our problem. So To Solve this Problem Formulae is very simple.
- We know that open brackets must be equal to closed bracket. So For this we will simply increment our open bracket count on encountering open bracket otherwise will decrement it
- Similarly we will simply increment our close bracket count on encountering close bracket otherwise will decrement it
- Moment our open bracket becomes less than 0, it means open bracket cannot be equal to close bracket count return false.
- Moment our close bracket becomes less than 0, it means close bracket cannot be equal to open bracket count return false.
- Otherwise return true
Approach
- Here we will take two variables open count and closed count and take a variable length which is pointing to the last index
- If string is either * or ( we will increment the open count otherwise decrement the open count.
- If string is either * or ) we will increment the close count otherwise will decrement it.
- The moment either our open count or closed count becomes zero we will return false means it is not a valid paranthesis string
- lets understand through dry run
- "
*()()))" output = false - open=1 close=1
- open=2 close=2
- open=1 close=3
- open=2 close=2
- open=1 close=2 (7-4)=3 open bracket close also decreases
- open=0 close =4
- open=-1 => return false;
string predictPartyVictory(string senate) {
bool checkValidString(string s) {
int length = s.length() - 1;
int openCount = 0, closedCount = 0;
for (int i = 0; i <= length; i++)
{
if (s[i] == '*' || s[i] == '(') openCount++;
else openCount--;
if (s[length - i] == '*' || s[length - i] == ')') closedCount++;
else closedCount--;
if (openCount < 0 || closedCount < 0) return false;
}
return true;
}
Complexity
- Time complexity:
Θ(n) - Space complexity:
Θ(1)
Problem 6: Can Place Flowers
Statement:
We have been given an array flowers where value 1 represent already flower present and 0 represent no flower present. we have to insert or put n flowers in the position where current position as well as its neighbours are empty.
Example 1
Input: flowers = [1,0,0,0,1], n = 1
Output: here we place flower at index 2.
Solution
Explanation
- To INSERT n Number of flowers in garden, We are simply checking if adjacent neighbours are empty , If they are empty we can insert the flower at i the position and decrement our n
- If n becomes 0 or less than 0 , then we will return true otherwise false.
Approach
- Here we will find the empty slots where we can place the flowers But Questions has condition neighbour of that plot also must be empty
- for this we are checking condition flowers[i-1] + flowers[i] + flowers[i+1] == 0
- we are inserting one more position at the begining and the ending for maintaining this edge case that if position 1st is empty and 2nd also then we can successfully place our flower at first position of array
- flower.insert(flower.begin(),0);
flower.push_back(0);
bool canPlace(vector<int>& flower, int n) {
flower.insert(flower.begin(),0);
flower.push_back(0);
for(int i=1; i<flower.size()-1; i++)
{
if(flower[i-1] + flower[i] + flower[i+1] == 0)
{
--n;
++i;
}
}
return n<=0;
}
Complexity
- Time complexity:
Θ(n) - Space complexity:
Θ(1)
Problem 7: Patching Array
Statement:
We have to add number in such a way, such that sum of all array element in subarray must be equal to n.
Return the minimum number of values required to make array equal to sum.
Example 1
Input: nums = [1,3], n = 8
Output: here we will add 4 to get 8
[1,3,4]
example2
Input: nums = [1,6], n = 12
Output: here we will add 5 to get 12 [1,5,6]
Solution
Explanation
- Approach for solving this problem is very clear. We need to add number such that after adding them in our array sum becomes n
- How We can do this JUST think about ? If an array from 1 to k given to us and inside the array elements are present between 1 to k and only some elements our present for example [1,3,6] Here we have element from 1 to 6.
- Now n can be any value and in order to make sum of array elements equal to n , we will insert number like 2 , 4, 5 . we can also insert 7.
- Now we have to think of approach of adding such elements which will make our array sum equal to n.
- Simple Intuition that i have used is -
- [1,2,5,15] n=25
- reach=0 initially
- Reach is variable , You will understand its role after reading
- reach=1 - before adding 1 to reach check if i is less than size of array and nums[i] <= reach+1
- reach = 3 after checking conditions (added 2 )
- 5 <= 3+1 no
- we will insert 4 in reach
- reach= 7
- 5 <= 7+1 reach=7+5=12
- 15<=12+1 no
- add 13 in reach reach=12+13=25
- We need to understand this thing that we need to cover n elements n is range, we have to cover the entire range.
- Note that at last we have to return the count of elements we have added in the original array. Here we have added 2 new elements.
Explanation
int minPatches(vector<int>& nums, int n) {
int count = 0,i=0;
long reach=0;
int size = nums.size();
while(reach < n) {
if(i < size && nums[i] <= reach+1) {
reach += nums[i];
i++;
}
else if(i >= size) {
reach += reach+1;
count++;
}
else {
reach += reach+1;
count++;
}
}
return count;
}
Complexity
- Time complexity:
Θ(n) - Space complexity:
Θ(1)
Applications of greedy algorithms
Greedy is used in algorithms where we take decision based on current scenario we dont think of future consequeneces. There are various problems of dp which can be solved using greedy.
