Simplification: You always take the nextTarget as the 0th element and then proceed to find the true nextTarget. However, this will fail if the nextTarget point and the leftmost point is same. In that case the while loop will end just after the first point as the nextTarget doesnot change its value and at the end of the loop when it sees nextTarget==starrt, it will break. In order to account for this you have addded the concept of collinear points too in your program. But it will be very easy if you just initialise nextTarget=start+1 or (start+1)%n (for overflows) always inside the while loop. This will simplify the code. Thank you
@@tusharroy2525 can you please make a video on *Suffix Array construction and applications* ? your suffix tree video was nice but you see, it's not so easy to implement. :( :( cover construction of Suffix array in nLogn or O(n) both version (DC3 algorithm) :/ also Persistent Segment Trees, Wavelet Trees etc :/ :/ *Suffix array a priority though ;)*
To be honest , I have been looking at various convex hull videos, everyone is just explaining the code part , no one is talking abt the intution .... You have explained it in the best way possible
Thx for the video and your work! Small typo: to find a vector ac (vector from point a to point c), you need to subtract ending point c from starting point a: (c_x - a_x, c_y - a_y). Otherwise you end up with vector pointing out to opposite direction. Because the same typo procedure was repeated for all vector, cross product will be the same (cos -1 * - 1 = 1 * 1 , -1 * 1 = 1 * -1).
So, i havent done vector mathematics in math class yet, but from what i understand, the cross-product of two vectors is a line perpendicular to both of them. But since there are always two way a line can go in 3d space to be prependicular to the two other vectors, how do you decide which way it goes (negative or positive). I see you have a thumb rule, but could you mathematically explain this to me?
in order to maintain points along the boundary in the same order, should we sort the collinear points in order of distance from the current point before adding to the results?
@13:55 Would it have any impact to always set "Point nextTarget" as "start" instead of "points[0]"? This has probably been a part confusing me since I struggled to intuit how the Jarvis March algorithm is guaranteed convergence, and, is guaranteed to find only those boundary points as well.
Hey, great video. I'm looking for Gift wrapping algorithm in three dimensions. Do you have any hints oder advices on how I can trasfer 2d to 3d solution?
Great explanation of convex hull. Though the second part was bugging my OCD sensors. I think you've got some calculation errors. Vector AB is , whereas you have written it as , which is in fact the vector BA. Same with AC and AD, which you have turned into CA and DA. By coincidence the cross product is the same when you reverse both, but you would have trouble if you used those vectors individually for other things. Also a note on the cross product that is useful to know (maybe). Cross product is strictly a 3-dimensional vector operation, but we are "hacking it" in two dimensions by assuming z=0 and then returning the resulting cross product's z value as a scalar to determine the angular direction. Because the input z-values are 0, the output x and y values are automatically 0 (due to multiplication), so the only nonzero output result is the z value.
So what i think is just figuring out least point in x direction (-ev) will define left bound , max point in x direction (+ev) will define the right bound.Similarly the least point in y direction (-ev) will define lower bound and positive y point will define upper bound.I dont what will be the data input format.
I found code for Jarvis march on one of the russian sites This code is written in my favourite programming language On wikipedia code for Monotone chain can be found Monotone chain can be treated as simplified Graham's scan I had to introduce node counter to my doubly linked list to rewrite code for Monotone chain from wikipedia It was quite easy to rewrite code for Jarvis march from russian site
Tushar for the vector ab the correct value would be b-a instead of a-b please refer to math.stackexchange.com/questions/1703120/calculating-vector-ab-from-vector-a-and-b. The result is the same since you compute all of them wrong or with a factor of -1.
if u r interested in competitive programming or targeting a good company ds and algos are must... language is just a way to transfer ur thoughts to computer .. if u know c++ then try to make ur STL as good as possible ...and then implement try to implement these algorithms...in the free time try to learn java and php
There's always an Indian guy who can make you understand that algorithm you seek . Tushar is definitely the best of them :)
Good to see you again. The video is terrific as always.
Super happy to see you back! Thanks so much
Simplification:
You always take the nextTarget as the 0th element and then proceed to find the true nextTarget. However, this will fail if the nextTarget point and the leftmost point is same. In that case the while loop will end just after the first point as the nextTarget doesnot change its value and at the end of the loop when it sees nextTarget==starrt, it will break. In order to account for this you have addded the concept of collinear points too in your program. But it will be very easy if you just initialise nextTarget=start+1 or (start+1)%n (for overflows) always inside the while loop. This will simplify the code. Thank you
Missed you so much!
Welcome back.
"hello friends my name is tushar "
kaan taras jaate hai inn awaazen ko sunane ko
happy to see u again
thanks
@@tusharroy2525 can you please make a video on *Suffix Array construction and applications* ? your suffix tree video was nice but you see, it's not so easy to implement. :( :( cover construction of Suffix array in nLogn or O(n) both version (DC3 algorithm) :/ also Persistent Segment Trees, Wavelet Trees etc :/ :/ *Suffix array a priority though ;)*
Thanks, Tushar! For helping students across the globe to develop their knowledge in competitive programming :)
appreciate your message.
I'm so happy you're back. If you ever do a meetup up let me know. lol. You're literally my hero.
Tushar, your videos are awesome! Congratulations and thanks! :)
Thank you Tushar ....Your videos have given me strength to get the Job....
+Ram Charan nice
He is back again! :)
yahhooooooo..
Thank you Tushar. Great explanation!
You are the best teacher ever.
+Aditya Ishan thanks buddy
Thanks Tushar.
Please do some System Design questions.
To be honest , I have been looking at various convex hull videos, everyone is just explaining the code part , no one is talking abt the intution .... You have explained it in the best way possible
I just wanna like this video from all my google accountss...........
good to see you again!
where r u from
Hi Tushar, Good to see you back. Hope you will make more videos on dynamic programming.
Great video, as always
Can you please make video on Line Sweep Algorithm, I find it bit difficult to understand?
thank you tushar sir , you are really amazing ..
Thx for the video and your work!
Small typo: to find a vector ac (vector from point a to point c),
you need to subtract ending point c from starting point a:
(c_x - a_x, c_y - a_y).
Otherwise you end up with vector pointing out to opposite direction.
Because the same typo procedure was repeated for all vector, cross
product will be the same (cos -1 * - 1 = 1 * 1 , -1 * 1 = 1 * -1).
So, i havent done vector mathematics in math class yet, but from what i understand, the cross-product of two vectors is a line perpendicular to both of them. But since there are always two way a line can go in 3d space to be prependicular to the two other vectors, how do you decide which way it goes (negative or positive). I see you have a thumb rule, but could you mathematically explain this to me?
great explanation sir. Please do this same for convex hull Graham's scan, line sweep.
And if possible plz make video regarding parallel algorithms.
Good to see you.
Thanks, Tushar!
in order to maintain points along the boundary in the same order, should we sort the collinear points in order of distance from the current point before adding to the results?
@13:55 Would it have any impact to always set "Point nextTarget" as "start" instead of "points[0]"? This has probably been a part confusing me since I struggled to intuit how the Jarvis March algorithm is guaranteed convergence, and, is guaranteed to find only those boundary points as well.
Hey, great video. I'm looking for Gift wrapping algorithm in three dimensions. Do you have any hints oder advices on how I can trasfer 2d to 3d solution?
Instead of a line, take a plane and find whether any point lies above that plane. Definitely a pretty complex code but could be an interesting solve.
Fantastic! What an explanation!! I suscribe lml
How do u make such a tough question so easy to understand...... Hats off...
hi Tushar, can you do a video for "LRU cache" problem?
Do a video tutorial about "Treaps" insertion and deletion. There are not much videos related to that.
Is there a similar algorithm for a 3D hull?
Great explanation of convex hull. Though the second part was bugging my OCD sensors.
I think you've got some calculation errors. Vector AB is , whereas you have written it as , which is in fact the vector BA. Same with AC and AD, which you have turned into CA and DA. By coincidence the cross product is the same when you reverse both, but you would have trouble if you used those vectors individually for other things.
Also a note on the cross product that is useful to know (maybe). Cross product is strictly a 3-dimensional vector operation, but we are "hacking it" in two dimensions by assuming z=0 and then returning the resulting cross product's z value as a scalar to determine the angular direction. Because the input z-values are 0, the output x and y values are automatically 0 (due to multiplication), so the only nonzero output result is the z value.
Thanks Scy. Yes, the order should be reversed
Exactly what was bugging me .
I started to doubt my years of intermediate Physics and mathematics haha.
Thank you for the comment.
boss is here
Thanks Tushar
Brilliant!!! Just Brilliant!!!
So what i think is just figuring out least point in x direction (-ev) will define left bound , max point in x direction (+ev) will define the right bound.Similarly the least point in y direction (-ev) will define lower bound and positive y point will define upper bound.I dont what will be the data input format.
Which formula is used for finding cross product?
nice explanation.thanks
what's the point of pushing collinear points in result? Aren't they redundant for convex hull?
Thanks buddy😃
I found code for Jarvis march on one of the russian sites This code is written in my favourite programming language
On wikipedia code for Monotone chain can be found Monotone chain can be treated as simplified Graham's scan
I had to introduce node counter to my doubly linked list to rewrite code for Monotone chain from wikipedia
It was quite easy to rewrite code for Jarvis march from russian site
I suppose it would be better to use collinearPoints.clear() in order to reset the collinear points.
love you, thanks
This algorithm is based on the technique called greedy?
Super useful
Hi Tushar, Thank you for providing nice video. But it would be better if you have a nice mic.
hi tushar , can you talk something abt your experience working at apple , not usual algo stuff .
+Navanshu unfortunately can't. There is NDA.
I am not getting why you used set to store result instead of array or vectors
you cannot use set as it is for storing point object.
sir if u ever get free time please add videos on geomertic algorithms and advanced trees algorithms
which geometric algorithms?
Thanks for the concern sir...
please make videos on line sweeping ,bipartite matching and light decomposition algorithm
Tushar is great
Thanks
Thanks, Sir for this nice video. Can you please help by making a video on Sweep line algorithm. Thanks in advance :)
Tushar for the vector ab the correct value would be b-a instead of a-b please refer to math.stackexchange.com/questions/1703120/calculating-vector-ab-from-vector-a-and-b. The result is the same since you compute all of them wrong or with a factor of -1.
Wait a sec, cross-product is a vector, not a number!
Need Graham and scan
sir I want to know learning to many language is important ya data structure and algorithm is more important with implemention...
if u r interested in competitive programming or targeting a good company ds and algos are must...
language is just a way to transfer ur thoughts to computer .. if u know c++ then try to make ur STL as good as possible ...and then implement try to implement these algorithms...in the free time try to learn java and php
thanks buddy
graham scan plzz
I don't understand, shouldn't the cross product be in 3d only? you're performing the calculation to get the determinant here
if I use the cross product formula setting the 3rd component to 0 it doesn't work
make graham's algo also
I think he lost his password...WHYYYY? Please make more videos
how can i modify this to get only the exterior points only ?
you are not a good teacher though you know things. thanks for sharing
hit like if u came to this video from UW CS341 also lmao
plllll-zzzzzzzz sir hindi me Lecture dea keje
I know c++