Asteroid Collision - Stack - Leetcode 735

0:00 - Read the problem
3:00 - Drawing Explanation
8:57 - Coding Solution

leetcode 735

#stack #lyft #python

[surters]

Missing the explanation how you came to the stack use, ie. the thoughts before this.

[updownftw]

I struggled with this problem for 3+ hours, even though I knew it uses stack.
That sucks, even though you know the approach. I looked at the solutions and most of them used while-else, or too complicated code. I wanted the sol to make sense to me.
This was the best explanation, and you didn't use the while-else loop which is very specific to Python. Thank you NeetCode :)

[jasonswift]

Your explanation is extremely clear. Hope to have a colleague like you very much in the company.

[yang]

The test case I didn't understand, despite drawing it out, is this one: [-2, -1, 1, 2], the answer should be [-2, -1, 1, 2], but I keep thinking its []

[orangethemeow]

How did you come up the idea setting a=0 ?

[ronakshah]

I think what youre calling diff is better named as "sum". So if the sum < 0, asteroid wins etc..

[giantbush]

I think using a Boolean to indicate whether to push into the stack is a cleaner way than the very clever way of setting a = 0.

[kanhakesarwani]

This has got to be one of the cleanest solutions!

[giantbush]

Figured it out without watching the vid but my solution was not neet. Good tricky interview qn.

[cometoafrica]

you could also use a break instead of a = 0 and then you wouldn't have to worry about that case after exiting the if-else block

[JKey]

is the time complexity here not O(n^2)? The stack that you are removing from could have up to N elements in it, and we need to iterate through the stack until we remove all the asteroids from the stack that we need to.

[sergten]

Great explanation, as always. There may be a small problem with overflowing when computing diff: 2, 147, 483, 647 + 1 = -2, 147, 483, 648. Not sure how Python handles that but other languages may wrap the result to negative.

[kiyoumarssohraby]

I think you made it over complicated by handling a=0 condition, you don't need this.
def asteroidCollision(self, asteroids):
ans = []
for a in asteroids:
while ans and a< 0 < ans[-1]:
if ans[-1] < -a:
ans.pop()
continue
elif ans[-1] == -a:
ans.pop()
break
else:
ans.append(a)
return ans

[MsSkip]

Managed to came up with a stack solution but damn wish you could just reverse a stack in java and return :(

[saswatamukherjee]

For people coding in other languages like C++ and Java, please put the code in the description which will be really helpful

[shivaarukonda]

Thank you for your wonderful explanation

[smitkadvani-tc]

Thank you for your solution, but based on question description what should be the anser for input sequence = [-5, -10, -5, 12]. It should be [12] but solution says [-5, -10, -5, 12]. I got confused.

[ujjwalrockriser]

LeetCode has not explained this question properly, but NeetCode has 😂

[curesnow]

I spent too much time on this problem and got stuck :(

[yihengyao]

Hi, I understand the algorithm, but I have a question in terms of the time complexity. I am a bit confused about why the time complexity is linear time? since we have a while loop inside a for loop. In the case of where we have n 1s and one -100 in the end, the outer loop would go n times to traverse to the last value, the inner loop would go n times as well to pop previous n values. So in this worst case, wouldn't the time complexity be n^2? Can anyone explain this? I really appreciate it. Thanks.