A little help for Disjoint interval(I too got stuck on it) When you first see the question,you make make the following observations in the following order 1)We need to select sets without overlap.This is done by observing the start and end 2)As we know how to understand whether there is overlap or not,next we aim to find how to understand which set to take and which to avoid? 3)Now we see one thing that we can select the sets based on thier start,end or length. The length is not practical as a long set may not overlap with any of the element. 4)Now in start and end. Just think that when we look at the next set to add,which element sets the rule/limit? Its obvious that end is setting the limit. 5)Now we have formed the thinking,we will do the code part //code bool compare(vector &v1,vector&v2){ return v2[1]>v1[1]; } int Solution::solve(vector &A) { sort(A.begin(),A.end(),compare); int ans=0,last=0;; for(vector it:A){ if(it[0]>last){ ans++; last=it[1]; } } return ans; }
Fun fact.. in Reinforcement Learning, if you know the optimal value function (which tells you how valuable it is to be in a given state), then the greedy policy with respect to that value function is the globally optimal policy! Sometimes the greedy approach is the best approach :)
11:30 I don't understand why the condition for flipping the bit is if the cost is odd, if the bit was 0 originally and the cost is odd then that means it's 1 now, so why flip it back?
We don't need to sort the whole array in the highest product question. We can iterate through the list once and find the highest 3 and lowest 2 numbers. And compare the maximum of both solutions. It would reduce the time complexity from O(NlogN) to O(N).
Correct 💯 Maybe he had to explain how to find highest 3 and lowest 2 numbers in an array that's why he skipped it. Like in the same way, he skipped Moore's voting algo in majority element question.
but it wouldn't be a greedy algorithm greedy algorithms boil down to selecting the best option at each iteration imo it's incredibly vague compared to something like dynamic programming which is almost like a specific technique but yeah
Glad to know these videos are helpful! I actually plan on doing more topic based interview coding questions. I'll be adding those videos on my channel :)
For the majority element problem, I believe the best solution will be to sort the element and pick the middle value since the majority element is the one that occurs more than N/2 times so it is a guarantee that it will sit in the middle of the list.
Amazing and very helpful video, I am daily referring this to learn greedy algorithm concepts, and finding it very trick as well, but your explanation, pace everything is fantastic. One small doubt for 28:51-38:31 largest permutation- def maxSwapsPossible(A,B): i = 0 max_i = len(A) d = {x:i for i, x in enumerate(A)} while B and i
Since, we want the maximum element's value at the variable, maybe we can use max_i = max(A) as a workaround instead? For eg, A = [2,5,3,4,1]. Dictionary will look like {2:0, 5:1, 3:2, 4:3, 1:4}. (Note: keys in the dictionary are the values of the numbers in list, and their indices are the values here). When we access the d[max_i] key, we get the corresponding value i.e. the index to it, which in this case would be 1 (index of max(A) which is 5). After this we can simply check if this maximum value is at the 0th index and swap their places, as well as their keys in the dictionary and increase the 0th index by 1 as well and continue similarly. right? Also the array needs to have a permutation of all the numbers till len(A), otherwise the code will break.
Awesome tanishq, need more videos on greedy technique, leetcode problems are still a lot challenging and really struggling to "when to apply" greedy. Please provide more videos and practice problems.
The bulb solution is remarkably unintuitive. Consider the bulbs in groups of similar values (e.g., 1111000 requires one flip; 000000011111 requires two; strict alternation is the worst case, as in 010101010). Then it's obvious you need to locate the first 0, then count the number of cases where a value differs from the preceding. It makes the solution provided by Sheyteo simple to understand, and avoids all the unnecessary modulo operations in the solution provided.
for the higest product we do not need to sort the array. we could just use 5 variable for finding the biggest 3 and the lowest 2. that way the time complexity would be o(n) that is better than O(nlogn).
True, but won't scale. Let's say instead of constant 3, multiply M numbers? in such case sort the array and split the M based Even/Odd and try to find max product. Generally interviewers go for such follow up questions, and sorting and finding gives you scalable solution.
Thanks for this tutorial. I've found it quite helpful during my job search. Only one improvement would be to just simply loop forward and backward once each. I think that's a lot simpler to understand and more space efficient.
11:30 I don't understand why the condition for flipping the bit is if the cost is odd, if the bit was 0 originally and the cost is odd then that means it's 1 now, so why flip it back?
Great video, but I think the largest permutation problem is not all that well explained. What does "largest permutation" even mean? Is it a permutation that results in the biggest numeric value when all elements are put together (because that's what's implied)? Because if so, then the solution is incorrect.
What amazing solutions for all the videos !!! especially for majority element. When you need space o(1) just use bits..wow will always keep this is mind. Thank you 🙏
Could you please correct the problem statement at 50:03 .It is NOT """Children with a higher rating than their neighbors get more candies. "" It should be """Children with a higher rating get more candies than their neighbors."""
11:30 I don't understand why the condition for flipping the bit is if the cost is odd, if the bit was 0 originally and the cost is odd then that means it's 1 now, so why flip it back?
Sorry, but I can't imagine myself on a 2d world where voices come from above 😭 All lame jokes aside, awesome stuff, this is really helpful for leetcoders ^^
distribute candy of time complexity O(n) solution. class Solution: # @param A : list of integers # @return an integer def candy(self, a): ans=[1]*len(a) for i in range(1,len(a)): if a[i]>a[i-1]: ans[i]=ans[i-1]+1 for i in range(len(a)-2,-1,-1): if a[i]>a[i+1]: ans[i]=max(ans[i],ans[i+1]+1) return sum(ans)
1:17:13 i'm fourteen years old, and the first solution that came to my mind to solve that problem is the mean, but my algo was to find the closest value to the mean hhhhh, and my algo works well.
Even faster algorithm for the bulbs problem (2x faster): def bulbs(self, A): cost = 0 prev = 1 for i in A: if i != prev: prev = i cost += 1 return cost
@@hsakaardnetih7898 in video, he is telling every passing ittreation of a 0,every remaining num will flip which means at every even occurence of cost, bit will same as inital, then we are keeping the bit, else we filping it at this point we fixed bit into it's proper state by predicting what should be bit's value if we would flip it every time when cost increased and then checking if bit 0 or 1, if bit is 0 flip it to 1 and increase cost if bit is 1 we can ignore it because it is already on
@@saifsd8267 your not dividing which can be a difficult process for computer you can test the code yourself it was about 2x faster on a large set of data
For the Largest Permutation problem, would this solution be considered greedy? def max_perm(arr, B): i = 0 if len(arr) > 1: while B and i < len(arr): max_val = max(arr[i:]) max_val_idx = arr.index(max_val) if arr[i] < max_val: arr[i], arr[max_val_idx] = arr[max_val_idx], arr[i] i += 1 B -= 1 return arr
In the disjointed intervals problem u made a mistake by always setting value of ending interval to previous value of ending interval, instead it should be like prevEnd = max(prevEnd , currentEnd), correct me if i am wrong
What if in 3rd problem the max sum of ranges is asked... Instead of max number of intervals What if the Continued ranges were acceptable? Example : { (1, 2), (2, 5), (5, 7) } all can be taken...
In the candies question, wouldn't it be faster if you iterate once L->R as said earlier and then iterate once R->L and set the value of element to be max of current and candies[i+1] to candies[i] due to most sorting implementations being O(nlogn) in the languages?
[Highest product] Translation to C++ with explanation: // A C++ program to find a maximum product of a // triplet in array of integers #include using namespace std;
/* Function to find a maximum product of a triplet in array of integers of size n */ int maxProduct(int arr[], int n) { // if size is less than 3, no triplet exists if (n < 3) return -1;
// Sort the array in ascending order sort(arr, arr + n);
// Return the maximum of product of last three // elements and product of first two elements // and last element return max(arr[0] * arr[1] * arr[n - 1], arr[n - 1] * arr[n - 2] * arr[n - 3]); }
// Driver program to test above functions int main() { int arr[] = { -10, -3, 5, 6, -20 }; int n = sizeof(arr) / sizeof(arr[0]);
I don’t think I do either. Does ‘switch’ mean every time you make a switch that results in all bulbs to the right switching, or does ‘switch’ mean every time a bulb in the array switches?
Answered by @mankritsingh, As we know how to understand whether there is overlap or not,next we aim to find how to understand which set to take and which to avoid so which to take and which to avoid, might be considered as greedy
[Bulbs] Translation to C++ with explanations: // CPP program to find number switch presses to // turn all bulbs on.
#include using namespace std;
int bulbs(int a[],int n) { // To keep track of switch presses so far int count = 0;
for (int i = 0; i < n; i++) { /* if the bulb's original state is on and count is even, it is currently on...*/ /* no need to press this switch */ if (a[i] == 1 && count % 2 == 0) continue;
/* If the bulb's original state is off and count is odd, it is currently on...*/ /* no need to press this switch */ else if(a[i] == 0 && count % 2 != 0) continue;
/* if the bulb's original state is on and count is odd, it is currently off...*/ /* Press this switch to on the bulb and increase the count */ else if (a[i] == 1 && count % 2 != 0) { count++; }
/* if the bulb's original state is off and count is even, it is currently off...*/ /* press this switch to on the bulb and increase the count */ else if (a[i] == 0 && count % 2 == 0) { count++; } } return count; }
// Driver code int main() { int states[] = {0,1,0,1}; int n = sizeof(states)/sizeof(states[0]);
overall most of explanations are tangled and hard to follow the logic. for me it is much easier to understand solution from code rather than looking at pictures. also pictures are not very descriptive. e.g. in candy problem the dp was used, probably unintentional, simplest greedy algorithm would be passing from left to right, then from right to left which would leave the same O(n) time but reduce memory to O(1) (from O(n))
I appreciate your effort, thank you. However is that only me finding problem statements very confusing? IMO Examples should visualize, not define problem statement. Find "the largest permutation possible" is very confusing
Correct me if I'm wrong, but for Largest Permutation problem with the A = [3,2,4,1,5] and B = 3... you could achieve [5,4,3,2,1] by swapping 1,5 [3,2,4,5,1] then swap 3,5 [5,2,4,3,1] then swap 2,4 [5,4,3,2,1]. If the rules prohibit swapping the same number multiple times, please disregard! :) Awesome video either way, very informative! Edit: Realizing this is all about "greedy algo"... which probably excludes the above, since my first swap is not aiming for the most valuable number first.
@@digambartupurwadi4071 in my haste, I was ignoring the fact that this video is about greedy algorithms. In the case of not using a greedy algorithm, you can achieve [5,4,3,2,1] by following my logic. The video example shows going for the highest value number first, even if it's not the "best" option.
Thank you for the video.I have a doubt in Highest product which is at 12:11 . Why are we not handling or looking at the possibilty of overflow here? it is given in question that the answer will be stored in a 32 bit variable so should we not consider that?
For the largest permutation if input is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] with swap = 1 the code would swap out 1 and 10, and would yield output [10, 2, 3, 4, 5, 6, 7, 8, 9, 1] which is actually a smaller permutation. Or am I missing something here?
@@ratnadeepsimhadri3465 No, comparisons are done numerically, as shown in the video. However, the method leads to the largest lexicographical value possible, not the largest number possible.
@Tanishq Chaudhary in the Gas Station problem. As you explained, we will move from indices 4 -> 0 -> 1 -> 2-> 3 -> 4. But can we move from index 1->0->4->3->2->1 . Will there be two possible answers? Please explain.
You could do that, but the answer would be different depending how you consider the problem. In reality, the distance between 3 and 4 would be represented by the cost '9', but if you ran the equation backward then you would be assigning that same distance (being travelled backward) only cost '1' because that is the cost being applied to index 4. If you run the equation with the same costs, despite the fact that this would not represent reality, then yes. That would be an alternative solution, though I doubt it would be considered a different solution, by many programmers, because they are so similar.
How is the first solution to the first question gives the minimal number? the algorithm here basically run through the all the bulbs , but that does not prove it is minimum
-> In the 2nd Problem (Highest Product) we can also solve it using heapq. def maximumProduct(nums: List[int]) -> int: a, b = heapq.nlargest(3, nums), heapq.nsmallest(2, nums)
return max(a[0]*a[1]*a[2], b[0]*b[1]*a[0]) -> In the 6th Problem (Distribute Candy) the solution you wrote has a time complexity of O(N log N) because of sorting and has Space complexity of O(n) because of the newly created data array but we can further optimize it to O(n) time complexity and O(1) space complexity by traversing from left to right and checking if the ratings of the immediate right neighbor is greater than the curr then increase the neighbor's candy by 1, after this loop traverse again in reverse( right to left) and check the same condition. def candy(ratings: List[int]) -> int: n = len(ratings) candy = [1]*n
for i in range(n-1): if ratings[i+1] > ratings[i]: candy[i+1] = max(candy[i+1], candy[i]+1)
for i in range(n-2, -1, -1): if ratings[i] > ratings[i+1]: candy[i] = max(candy[i], candy[i+1]+1)
Sir now I am pursuing integrated mtech 5 years course specialization in data science now I completed 3rd can you please say how to and how much I need to prepare to get decent job as fresher in data science sector because there are vast number of topics I am very confused like upto how many concepts I need to cover as a fresher to get decent job in data science sector
which coding skill is the best for you? And you told us about what languages you are learning as if it would change anything? Any, my brother in christ, any coding skill is equally good for you. What you might want to ask is, however, probably "what language should I learn based on my goals?"
Hey bro, what i recommend is go and learn any language you want ( though it would be best if you learn a low-level language such as C or C++. You could learn C for example). And after that begin to learn algorithms and data structures. Do not dive in those topics directly . First go and explore the thing that you want to learn. First off learn common simple algorithm like swaping 2 numbers(You might know it already), gcd algorithm, Just really basic stuffs. And then day by day learn a little bit more. Try to find problems and solve them in any language you know how to code. Basically , get good at problem solving.The best skill you can get is having good problems solving skills. İ can talk about programming for hours. This is just a beginning. There is a long way to go, man. Last but not least Do not ever stop learning. Programming is not about smartness. Yeah, smart people can program well, they might code well. But that does not mean only smart guya can do that. İt is about learning all the time. Be consistent. (Sorry me for misspelling words and vocabulary mistakes) Best luck ! .
If you are confortable with python and can code very well , lets say you can code binary trees avl tree on ur own then try exploring other languages and keep improving your algorithm by practising dp and backtracing as well as keeping tabs with hackerrank codechef . During this process keep reading lots of peoples code and make projects at spare time . Apply for jobs , after all this process is over and practise shining your communication and interpersonal skills . learn how to negotiate and be confident . Live life at every moment as if tomorrow is gonna be interview Day!?😵
I had a question. Regarding problems where you need to find min cost to do something, or min operations, or some similar variant, how do you know that the algorithm you choose guarantees the minimum? I'm sorry if that doesn't make sense but I realize I always second guess on if the algorithm I implement can truly minimize the cost needed? Is there a way to get better at this besides just gaining more experience?
A little help for Disjoint interval(I too got stuck on it)
When you first see the question,you make make the following observations in the following order
1)We need to select sets without overlap.This is done by observing the start and end
2)As we know how to understand whether there is overlap or not,next we aim to find how to understand which set to take and which to avoid?
3)Now we see one thing that we can select the sets based on thier start,end or length. The length is not practical as a long set may not overlap with any of the element.
4)Now in start and end. Just think that when we look at the next set to add,which element sets the rule/limit? Its obvious that end is setting the limit.
5)Now we have formed the thinking,we will do the code part
//code
bool compare(vector &v1,vector&v2){
return v2[1]>v1[1];
}
int Solution::solve(vector &A) {
sort(A.begin(),A.end(),compare);
int ans=0,last=0;;
for(vector it:A){
if(it[0]>last){
ans++;
last=it[1];
}
}
return ans;
}
Fun fact.. in Reinforcement Learning, if you know the optimal value function (which tells you how valuable it is to be in a given state), then the greedy policy with respect to that value function is the globally optimal policy! Sometimes the greedy approach is the best approach :)
Mostly epsilon greedy is used for exploration so yeah greedy in the limit with infinite exploration.
@@AnkitKumar-ph6zm exactly what I was thinking. In this case "greedy" seems like a misnomer
11:30 I don't understand why the condition for flipping the bit is if the cost is odd, if the bit was 0 originally and the cost is odd then that means it's 1 now, so why flip it back?
Thank you so much for your efforts. And thanx Beau for posting such useful content on this channel
We don't need to sort the whole array in the highest product question. We can iterate through the list once and find the highest 3 and lowest 2 numbers. And compare the maximum of both solutions. It would reduce the time complexity from O(NlogN) to O(N).
Correct 💯
Maybe he had to explain how to find highest 3 and lowest 2 numbers in an array that's why he skipped it.
Like in the same way, he skipped Moore's voting algo in majority element question.
but it wouldn't be a greedy algorithm
greedy algorithms boil down to selecting the best option at each iteration
imo it's incredibly vague compared to something like dynamic programming which is almost like a specific technique but yeah
it’d be so so helpful if there were more videos like this on different topics
Glad to know these videos are helpful!
I actually plan on doing more topic based interview coding questions. I'll be adding those videos on my channel :)
Check out the other video from FreeCodeCamp - they have good content on Dynamic Programming, Graphs, and Binary Trees among others.
For the majority element problem, I believe the best solution will be to sort the element and pick the middle value since the majority element is the one that occurs more than N/2 times so it is a guarantee that it will sit in the middle of the list.
sorting array will take NlogN time,, while moore algo take N only.
Amazing and very helpful video, I am daily referring this to learn greedy algorithm concepts, and finding it very trick as well, but your explanation, pace everything is fantastic.
One small doubt for 28:51-38:31 largest permutation-
def maxSwapsPossible(A,B):
i = 0
max_i = len(A)
d = {x:i for i, x in enumerate(A)}
while B and i
In the video, the array was first sorted, so the max element will be present in len(A)
Since, we want the maximum element's value at the variable, maybe we can use max_i = max(A) as a workaround instead? For eg, A = [2,5,3,4,1]. Dictionary will look like {2:0, 5:1, 3:2, 4:3, 1:4}. (Note: keys in the dictionary are the values of the numbers in list, and their indices are the values here). When we access the d[max_i] key, we get the corresponding value i.e. the index to it, which in this case would be 1 (index of max(A) which is 5). After this we can simply check if this maximum value is at the 0th index and swap their places, as well as their keys in the dictionary and increase the 0th index by 1 as well and continue similarly. right? Also the array needs to have a permutation of all the numbers till len(A), otherwise the code will break.
Dood read the question first, the array consists of N natural nos .So your example is not valid for this code.
Awesome tanishq, need more videos on greedy technique, leetcode problems are still a lot challenging and really struggling to "when to apply" greedy. Please provide more videos and practice problems.
The bulb solution is remarkably unintuitive. Consider the bulbs in groups of similar values (e.g., 1111000 requires one flip; 000000011111 requires two; strict alternation is the worst case, as in 010101010). Then it's obvious you need to locate the first 0, then count the number of cases where a value differs from the preceding. It makes the solution provided by Sheyteo simple to understand, and avoids all the unnecessary modulo operations in the solution provided.
Yes I could not get it
i thought of the same thing
for the higest product we do not need to sort the array. we could just use 5 variable for finding the biggest 3 and the lowest 2. that way the time complexity would be o(n) that is better than O(nlogn).
True, but won't scale. Let's say instead of constant 3, multiply M numbers? in such case sort the array and split the M based Even/Odd and try to find max product. Generally interviewers go for such follow up questions, and sorting and finding gives you scalable solution.
Thanks for this tutorial. I've found it quite helpful during my job search. Only one improvement would be to just simply loop forward and backward once each. I think that's a lot simpler to understand and more space efficient.
Algorithms are useful to understand better some things ... nice challenge
11:30 I don't understand why the condition for flipping the bit is if the cost is odd, if the bit was 0 originally and the cost is odd then that means it's 1 now, so why flip it back?
For maximum product problem, consider input as [-1,-2,-4,-3,0], both the hypothesis would be 0 and max would again be 0, interesting.
Yes, any other combination would give negative answer
In that case the answer is simply is zero, you could even put a clausule to return zero if that's the highest value in the array
In gas station question, you can avoid extra iteration like keeping condition
if start>=n:
break
Thanks for the amazing tutorial 👍
Great video, but I think the largest permutation problem is not all that well explained. What does "largest permutation" even mean? Is it a permutation that results in the biggest numeric value when all elements are put together (because that's what's implied)? Because if so, then the solution is incorrect.
in the Largest permutations problem. we have the largest index and length of the array as 5 , if we give any value greater than 5 , will throw an err
This channel is awesome! Thanks for sharing your knowledge!
Dude thanks for this video I've never found a better explanation of greedy algorithms that this one.
Also your problem solving skills are great.
Also I forgot to mention I appreciate the effort.
What amazing solutions for all the videos !!! especially for majority element. When you need space o(1) just use bits..wow will always keep this is mind. Thank you 🙏
My solution for the bulbs problem -
def bulbs(A):
cost = 0
flip = 0
for i in A:
if flip == i:
cost += 1
flip = flip + 1 & 1
return cost
Could you please correct the problem statement at 50:03 .It is NOT """Children with a higher rating than their neighbors get more candies.
""
It should be """Children with a higher rating get more candies than their neighbors."""
11:30 I don't understand why the condition for flipping the bit is if the cost is odd, if the bit was 0 originally and the cost is odd then that means it's 1 now, so why flip it back?
Thanks for the tutorial!
The highest product problem can also be solvable in Linear O(n) time without sorting but using if else.
Sorry, but I can't imagine myself on a 2d world where voices come from above 😭
All lame jokes aside, awesome stuff, this is really helpful for leetcoders ^^
distribute candy of time complexity O(n) solution.
class Solution:
# @param A : list of integers
# @return an integer
def candy(self, a):
ans=[1]*len(a)
for i in range(1,len(a)):
if a[i]>a[i-1]:
ans[i]=ans[i-1]+1
for i in range(len(a)-2,-1,-1):
if a[i]>a[i+1]:
ans[i]=max(ans[i],ans[i+1]+1)
return sum(ans)
wow yesterday i got homework for greedy algorithm, and here we are
1:17:13 i'm fourteen years old, and the first solution that came to my mind to solve that problem is the mean, but my algo was to find the closest value to the mean hhhhh, and my algo works well.
One of the best coding channel in RUclips....
Even faster algorithm for the bulbs problem (2x faster):
def bulbs(self, A):
cost = 0
prev = 1
for i in A:
if i != prev:
prev = i
cost += 1
return cost
THNAK YOU!!! i was so lost when i watched the sol in video.
wow this is more optimised that his code
@@hsakaardnetih7898 in video, he is telling every passing ittreation of a 0,every remaining num will flip
which means at every even occurence of cost, bit will same as inital, then we are keeping the bit, else we filping it
at this point we fixed bit into it's proper state by predicting what should be bit's value if we would flip it every time when cost increased
and then checking if bit 0 or 1,
if bit is 0 flip it to 1 and increase cost
if bit is 1 we can ignore it because it is already on
How is this 2x faster?
@@saifsd8267 your not dividing which can be a difficult process for computer
you can test the code yourself it was about 2x faster on a large set of data
For the Largest Permutation problem, would this solution be considered greedy?
def max_perm(arr, B):
i = 0
if len(arr) > 1:
while B and i < len(arr):
max_val = max(arr[i:])
max_val_idx = arr.index(max_val)
if arr[i] < max_val:
arr[i], arr[max_val_idx] = arr[max_val_idx], arr[i]
i += 1
B -= 1
return arr
Those visualizations did really help, gg❤
In the disjointed intervals problem u made a mistake by always setting value of ending interval to previous value of ending interval, instead it should be like prevEnd = max(prevEnd , currentEnd), correct me if i am wrong
What if in 3rd problem the max sum of ranges is asked... Instead of max number of intervals
What if the Continued ranges were acceptable? Example : { (1, 2), (2, 5), (5, 7) } all can be taken...
The bulb problem keep my mind glowing
Wow.......That' s so cool. Keep going Sir. TNice tutorials motivtes too.
12:30 - using heapq the task "max product" will work faster
Thanks for the content!
awesome. Adding this to my playlist
Very well illustrated! Thanks
Wow, so well done! Thanks for posting, man! Very helpful.
excellent video, thanks for the effort man. Helped me a lot
Hie @tanishq.... Loved the style of your coding. Learnt a lot from your coding style. Thank you❤
🎉🎉 amazing
Thankyou 🙂
In the candies question, wouldn't it be faster if you iterate once L->R as said earlier and then iterate once R->L and set the value of element to be max of current and candies[i+1] to candies[i] due to most sorting implementations being O(nlogn) in the languages?
Is there another explanation of the bulbs problem? As in those classic CS problems like the Stable Marriage (Gale-Shapely)?
[Highest product]
Translation to C++ with explanation:
// A C++ program to find a maximum product of a
// triplet in array of integers
#include
using namespace std;
/* Function to find a maximum product of a triplet
in array of integers of size n */
int maxProduct(int arr[], int n) {
// if size is less than 3, no triplet exists
if (n < 3)
return -1;
// Sort the array in ascending order
sort(arr, arr + n);
// Return the maximum of product of last three
// elements and product of first two elements
// and last element
return max(arr[0] * arr[1] * arr[n - 1],
arr[n - 1] * arr[n - 2] * arr[n - 3]);
}
// Driver program to test above functions
int main() {
int arr[] = { -10, -3, 5, 6, -20 };
int n = sizeof(arr) / sizeof(arr[0]);
int max = maxProduct(arr, n);
if (max == -1)
cout
Please do a course on Divide and Conquer!
Hi,
Didn't understand why the first algorithm, with bulbs and flips
is considered a greedy algorithm.
Can someone explain please? :))
Thanks!
I don’t think I do either. Does ‘switch’ mean every time you make a switch that results in all bulbs to the right switching, or does ‘switch’ mean every time a bulb in the array switches?
Answered by @mankritsingh,
As we know how to understand whether there is overlap or not,next we aim to find how to understand which set to take and which to avoid
so which to take and which to avoid, might be considered as greedy
He really explains in a 3Blue1Brown Way.... Ngl
Haha! This is the best compliment I have gotten. Happy that you are liking it. Thanks a lot 😄
@@chaudharycodes I really mean it though
The Dialogues and Animation and the Way you Explain is just Fabulous ❤..
(Btw you seem to be from India...)
Thanks!!!
So helpful, really thank you.
[Bulbs]
Translation to C++ with explanations:
// CPP program to find number switch presses to
// turn all bulbs on.
#include
using namespace std;
int bulbs(int a[],int n)
{
// To keep track of switch presses so far
int count = 0;
for (int i = 0; i < n; i++)
{
/* if the bulb's original state is on and count
is even, it is currently on...*/
/* no need to press this switch */
if (a[i] == 1 && count % 2 == 0)
continue;
/* If the bulb's original state is off and count
is odd, it is currently on...*/
/* no need to press this switch */
else if(a[i] == 0 && count % 2 != 0)
continue;
/* if the bulb's original state is on and count
is odd, it is currently off...*/
/* Press this switch to on the bulb and increase
the count */
else if (a[i] == 1 && count % 2 != 0)
{
count++;
}
/* if the bulb's original state is off and
count is even, it is currently off...*/
/* press this switch to on the bulb and
increase the count */
else if (a[i] == 0 && count % 2 == 0)
{
count++;
}
}
return count;
}
// Driver code
int main()
{
int states[] = {0,1,0,1};
int n = sizeof(states)/sizeof(states[0]);
// Function Code
cout
overall most of explanations are tangled and hard to follow the logic. for me it is much easier to understand solution from code rather than looking at pictures. also pictures are not very descriptive.
e.g. in candy problem the dp was used, probably unintentional, simplest greedy algorithm would be passing from left to right, then from right to left which would leave the same O(n) time but reduce memory to O(1) (from O(n))
I appreciate your effort, thank you.
However is that only me finding problem statements very confusing? IMO Examples should visualize, not define problem statement.
Find "the largest permutation possible" is very confusing
This was extremely helpful to me ! Thanks a lot
Correct me if I'm wrong, but for Largest Permutation problem with the A = [3,2,4,1,5] and B = 3... you could achieve [5,4,3,2,1] by swapping 1,5 [3,2,4,5,1] then swap 3,5 [5,2,4,3,1] then swap 2,4 [5,4,3,2,1]. If the rules prohibit swapping the same number multiple times, please disregard! :) Awesome video either way, very informative!
Edit: Realizing this is all about "greedy algo"... which probably excludes the above, since my first swap is not aiming for the most valuable number first.
Thank you for the *edit*. Most people won't even mention anything after a problem is resolved, leaving readers in pain 🥲. So thank you 🙏🏻
I think the last swap of 2,4 will make it [5,4,2,3,1] and not [5,4,3,2,1].
@@digambartupurwadi4071 in my haste, I was ignoring the fact that this video is about greedy algorithms. In the case of not using a greedy algorithm, you can achieve [5,4,3,2,1] by following my logic. The video example shows going for the highest value number first, even if it's not the "best" option.
I think there is a problem on leetcode array rotation by k, where this approach was used.
@@nathaniel-.- ur ignoring the fact that ur simply wrong...check again your swaps :)
so I decided to give soft softs a try. I just subscribed to your channel
the majority element solution blew my mind
That was great. Thank you.
Thank you
Want to hug you man..Thank you from bottom of my heart.
Great video. Thanks
Thank you for the video.I have a doubt in Highest product which is at 12:11 . Why are we not handling or looking at the possibilty of overflow here? it is given in question that the answer will be stored in a 32 bit variable so should we not consider that?
Great video!
What a coincidence!
I was just about to start practicing Greedy Algo problems on Leetcode. Thank you for this video freecodecamp!
Me too, man!
the same here, many thanks to him.
Great Video! Just in time to lean for my exams
Everything works at its best!!
For the largest permutation if input is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] with swap = 1
the code would swap out 1 and 10, and would yield output [10, 2, 3, 4, 5, 6, 7, 8, 9, 1] which is actually a smaller permutation.
Or am I missing something here?
That's correct. Even if we take [1, 2, 9, 10] and 1 swap, the output will be [10, 2, 9, 1] which is smaller than [9, 2, 1, 10].
Actually in this problem, largest means largest lexicographical value, not the largest numeric value.
@@a6hiji7 So We are supposed to compare the elements of the array lexicographically ?
@@ratnadeepsimhadri3465 No, comparisons are done numerically, as shown in the video. However, the method leads to the largest lexicographical value possible, not the largest number possible.
@@a6hiji7 how is [10,2,9,1] lexicographically greater than [9,2,1,10]? It is the other way around.
Your light bulb explanation and code is purely ambiguous.
Thanku for your efforts this helps a lot
great content!!
Thank you 🙏🏻
@Tanishq Chaudhary in the Gas Station problem. As you explained, we will move from indices 4 -> 0 -> 1 -> 2-> 3 -> 4. But can we move from index 1->0->4->3->2->1 .
Will there be two possible answers?
Please explain.
You could do that, but the answer would be different depending how you consider the problem.
In reality, the distance between 3 and 4 would be represented by the cost '9', but if you ran the equation backward then you would be assigning that same distance (being travelled backward) only cost '1' because that is the cost being applied to index 4.
If you run the equation with the same costs, despite the fact that this would not represent reality, then yes. That would be an alternative solution, though I doubt it would be considered a different solution, by many programmers, because they are so similar.
TNice tutorials is so amazing thanks for the videooo ;D
Many thanks!
I can't wrap my head around "crosses = [(cross-index) for index,cross in enumerate(crosses)]" this part of the Seats problem. Any insights?
Nice video!!
This came at the perfect time
Excellent Lecture Binary Tree question next
How is the first solution to the first question gives the minimal number? the algorithm here basically run through the all the bulbs , but that does not prove it is minimum
Thanks for this video
49:59 Distribute Candy (Pin)
Nice work
thank you so much
Largest permutation solution is wrong d[_max] is null pointer
Nice Explanation
Thanks!!
-> In the 2nd Problem (Highest Product) we can also solve it using heapq.
def maximumProduct(nums: List[int]) -> int:
a, b = heapq.nlargest(3, nums), heapq.nsmallest(2, nums)
return max(a[0]*a[1]*a[2], b[0]*b[1]*a[0])
-> In the 6th Problem (Distribute Candy) the solution you wrote has a time complexity of O(N log N) because of sorting and has Space complexity of O(n) because of the newly created data array but we can further optimize it to O(n) time complexity and O(1) space complexity by traversing from left to right and checking if the ratings of the immediate right neighbor is greater than the curr then increase the neighbor's candy by 1, after this loop traverse again in reverse( right to left) and check the same condition.
def candy(ratings: List[int]) -> int:
n = len(ratings)
candy = [1]*n
for i in range(n-1):
if ratings[i+1] > ratings[i]:
candy[i+1] = max(candy[i+1], candy[i]+1)
for i in range(n-2, -1, -1):
if ratings[i] > ratings[i+1]:
candy[i] = max(candy[i], candy[i+1]+1)
return sum(candy)
Thank you so much❤
1:36:05
Sir now I am pursuing integrated mtech 5 years course specialization in data science now I completed 3rd can you please say how to and how much I need to prepare to get decent job as fresher in data science sector because there are vast number of topics I am very confused like upto how many concepts I need to cover as a fresher to get decent job in data science sector
why for distribute candy we didnt sort the array and increase one by one for finding sum ?
As far as i know, the FIRST tNice tutorialng We should do is SET THE TEMPO, it is very crucial.
but what if the array is like:(4,3,2,1,0)
and u should raplace 3 time to get the maximum?
its will not work.
I am begginer in coding but i learning python and html , css which coding skill is best for me ?
Tell me !
which coding skill is the best for you? And you told us about what languages you are learning as if it would change anything? Any, my brother in christ, any coding skill is equally good for you. What you might want to ask is, however, probably "what language should I learn based on my goals?"
As your wish!!!
@@nepalisachinvlog757 okk bro
Hey bro, what i recommend is go and learn any language you want ( though it would be best if you learn a low-level language such as C or C++. You could learn C for example). And after that begin to learn algorithms and data structures. Do not dive in those topics directly . First go and explore the thing that you want to learn. First off learn common simple algorithm like swaping 2 numbers(You might know it already), gcd algorithm, Just really basic stuffs. And then day by day learn a little bit more. Try to find problems and solve them in any language you know how to code. Basically , get good at problem solving.The best skill you can get is having good problems solving skills. İ can talk about programming for hours. This is just a beginning. There is a long way to go, man. Last but not least Do not ever stop learning. Programming is not about smartness. Yeah, smart people can program well, they might code well. But that does not mean only smart guya can do that. İt is about learning all the time. Be consistent. (Sorry me for misspelling words and vocabulary mistakes) Best luck ! .
If you are confortable with python and can code very well , lets say you can code binary trees avl tree on ur own then try exploring other languages and keep improving your algorithm by practising dp and backtracing as well as keeping tabs with hackerrank codechef . During this process keep reading lots of peoples code and make projects at spare time .
Apply for jobs , after all this process is over and practise shining your communication and interpersonal skills . learn how to negotiate and be confident .
Live life at every moment as if tomorrow is gonna be interview Day!?😵
Хорошие разборы задач на алгоритмы и структуры данных, спасибо!
amazing thank you!
Amazing
I had a question. Regarding problems where you need to find min cost to do something, or min operations, or some similar variant, how do you know that the algorithm you choose guarantees the minimum? I'm sorry if that doesn't make sense but I realize I always second guess on if the algorithm I implement can truly minimize the cost needed? Is there a way to get better at this besides just gaining more experience?
If they ask us in the question to find minimum, maximum, possible no of ways we need to first choose greedy algorithm or recursion