Astroid Collision
ฝัง
- เผยแพร่เมื่อ 20 ก.ย. 2024
- For business inquiries email partnerships@k2.codes SOCIAL
----------------------------------------------------------------------------------------------------------------
Instagram: / kevinnaughtonjr
Twitter: / kevinnaughtonjr
Patreon: / kevinnaughtonjr
Merch: teespring.com/...
GitHub: github.com/kdn251
MUSIC
----------------------------------------------------------------------------------------------------------------
kanye west ft. lil pump - "i love it" (lofi remix by ofey) by ofey
/ i-love-it
LYFT > UBER FIGHT ME IN THE COMMENTS BELOW
instagram: instagram.com/kevinnaughtonjr/
twitter: twitter.com/KevinNaughtonJr
patreon: www.patreon.com/KevinNaughtonJr
merch: teespring.com/stores/kevin-naughton-jrs-store
I live in India, we don't have lyft here. Case closed. 😂
I was never interviewed by lyft nor uber. I just started driving after background check 24 hours later
niiiice
gold
Lyft's most asked question is "how many coupons will it take to get someone to use lyft over uber?"
This was good J
i am not able to understand if you are only pushing positive value in the stack than why checks for negative in the stack?
Oh my gosh, I have to learn a lot from you...Lots of Determination, Dedication, Discipline. You are consistent on what you are doing and there is no Friday nights fun. Great dude keep it going, I will follow you 🤗
Surendra thanks really appreciate the kind words and your support!!!
using a stack is pretty intuitive, but the nuances are a little complicated. this deserves medium difficulty because of the repeated collisions from a new asteroid. good job on this video.
Thank you very. much. I like how to justify which data structure to use with some explanation, instead of just saying let's go ahead and use a stack for this problem. Huge fan of your channel. Keep up the fantastic work.
How do you come up with solutions to the hard or medium questions on leetcode? And keep it going dude ur channel is amazing 😊.
Chicken Dolo lots of practice and thanks :)
OMG I was literally on Lyft's questions and was doing this.. lol. Thanks Kevin. Can you also do Oracle's most asked question - #425 - Word Squares (hard)? Thanks in advance man
Nikhil Mathur haha no way that’s amazing I’ll put it on my list
When you asked us to pause the video and think of a solution, I thought of solving this by starting from the left to right and detecting the first collision (the first positive asteroid that is followed by a negative one), then we “collide them”, see which one survives and pass the array after the collision recursively to the same function. With the base condition being that we detect no more collisions in the array. (Or a for loop instead of recursion to save on memory of call stack)
I wanted to ask you, first is this a crap solution? And second the time complexity of such solution would be O(n^2)?
You're right. The time complexity is definitely O(n^2) cause Kevin is using a nested loop.
@@neslzkusfep a monotonic stack is O(n)
@@mannyruiz7880 Yep I was wrong about the time complexity 2 years ago. Kevin's solution is O(n) because we are only pushing and popping each asteroid at most once. Access and search operations for a monotonic stack are O(n), but push and pop operations are O(1). The time complexity of the solution is O(n) because we are iterating through the entire array of asteroids once and then we are pushing and popping each asteroid at most once in O(1) time.
So O(n) (array iteration) + O(1) (stack operations) = O(n).
why does his drip go so hard
I just amazed for this simple solution 😃
Thanks for an amazing video! This might be dumb, but I still do not get why [-2,-1,1,2] returns itself. I thought it would return an empty array. In fact, [-3,-2,2,3] returns an empty array.
did you mean [-2,-1,1,2] and [3,2,-2,-3] ?
@@pratikchowdhury9210 Sorry, yes. Fixed
Not dumb! I'm assuming you mean [-2,-1,1,2] and it's because the first two (-2, and -1) are moving left (and will never collide with each other) and the other 2 (1 and 2) are moving right (and will never collide with each other). This example of the equivalent of us (representing an asteroid each) putting our backs against each other walking opposite directions i.e. we'll never collide
@@KevinNaughtonJr Thank you for your reply Kevin! I understand what you are saying. However, based on your explanation, is [-3,-2,2,3], asI mentioned above, supposed to return itself because there is no collide?
@@amontokoro9357 it should
subscribed to you! I like interview questions on my timeline and i love how your channel is dedicated to this. Also can u answer my other comment.
Thanks dude appreciate the support!
What is the difference between stack.push() and stack.add()?
Niiiiiiice problem. Didnt think in a Stack! Using it makes the problem more easy than medium. Thank you :)
btw: do you know if it can be odne in place? seems like yes
Anytime and in place meaning modifying the original array?
@@KevinNaughtonJr yes! I mean, not creating the stack
Awesome bro! It is really helpful for me to learn how to explain our solution to our interviewer!
Thanks Kevin dope name btw
Heya, no idea if you do this already or not but it would be really helpful to go over space and time complexity as well at the end :) Thanks for the video!
Thanks for the video! All great, regarding the final part, is it just me or the explanation why we need 'remaining' array populated backwards was kind of unclear? In Python, we would just simply return stack. Here, we populate the 'remaining' array from the end since stack returns items in this order: last, last-1, last-2, so to convert it into remaining, we also start with populating last item of remaining, then last-1, etc.
Thanks man, It was seriously helpful :)
Isn't complexity is
On^2?
Please make a series on Uber and Lyft interview questions! Thanks for your efforts. You're doing great!
Seemed like a divide and conquer problem to me
Between line 10-11, shouldn’t it be - Math.abs(aesteroids[i]). As we are trying to compare the stack value vs absolutely value of potential collision element. So while(….&& stack.peak() < Math.abs(aesteroids[i]))
@kevin
Haha! The sound at the last
Great explanation Kevin!
Why these kinda solutions never come in my mind!
great solution Kevin!
735. Asteroid Collision. Excellent! Thanks.
anytime!
Just completed a similar problem, 821. Shortest Distance to a Character
This O(n^2) implementation? I see 2 loops
just cuz u see 2 loops doesnt automatically mean n^2.
That's O(N) because each element is not processed N times. Each element is processed at most twice(pushing in and popping out), which results in linear time complexity.
Careful 2 loops doesn’t mean n^2 you have to think about what each of the loops are doing
Thanks for the explanation
i would like to see the explanation for course schedule I and II from leetcode
lalit borse I’ll see what I can do
Would you do basic calculator I, II and III from leetcode
Congrats we've now deleted this interview from our question bank. But keep studying!
Watched 5 minutes. ha-ha, your design is using Stack, it's much simpler then mine. Thanks for sharing.
I'll do it again with Stack.
class Solution:
def asteroidCollision(self, A: List[int]) -> List[int]:
# stack
s = []
for v in A:
if not s:
s.append(v)
elif s[-1] < 0:
s.append(v)
elif s[-1] > 0:
if v > 0:
s.append(v)
else:
while s and s[-1] > 0 and s[-1] < abs(v):
s.pop()
if not s or s[-1] < 0:
s.append(v)
elif s[-1] == abs(v):
s.pop()
return s
The last elseif case of in can be merged
Good content
I almost solved the problem my code was a mess. Yours is way too clean.
chinmay swaroop saini haha thanks
Asteroid*
we dont have lyft here in India XD
uber it is then i guess???
@@KevinNaughtonJr yup
Hitting submit without run? Psychopath.