See joint in leetcode. What would you do if an asteroid comes from the right and joins a stable asteroid row? It will keep colliding till the row becomes stable. So first come will get affected. Stack.
-2 and -1 are moving to the left. 1 and 2 are moving to the right. No collisions will happen, so no asteroids will explode. Therefore, the answer is same as the input [-2, -1, 1, 2]
I was also stuck on this. I feel it wasnt clear from the question that the order of the input mattered. I interpreted the question to ask to evaluate all *possible* collisions.
Yeah my dumb brain got confused on this test case too.. It's because we assumed that if the asteroid and the head of the stack have opposite directions, then they collide no matter what... however, that's not true because they only collide if the asteroid is moving to the left (negative) and the head of the stack is moving to the right (positive); otherwise, they will never collide
@@hanyo3629 stack=[] for i in asteroids: while stack and i0: #collision occured if abs(i)>stack[-1]: stack.pop() continue elif abs(i) == stack[-1]: stack.pop() break else: stack.append(i) return stack
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.
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.
ok, nvm I thought about it more and I see why it is O(n). The total number of elements that ever go into the stack can be N since each element in the input list of size N can go into the stack once. So it'd be O(n) for iterating through the input array and O(n) total iterations through the stack over the course of the whole function, hence O(n) + O(n) = O(n). Leaving this here in case someone else wonders about this like I did
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.
I think its because some how you're omitting negative asteroids; i made that mistake too. If 3 are going left(negative values), and one is going positive, then u got four asteroids that never collide. So the output IS the input.
Nice explanation. It would have been simpler if you added an else with while instead of making a = 0 and checking that condition later. Thanks anyway. class Solution: def asteroidCollision(self, asteroids: List[int]) -> List[int]: ans = [] k = 0 for val in asteroids: while ans and val < 0 and ans[-1] > 0: if ans[-1] + val < 0: ans.pop() elif ans[-1] + val == 0: ans.pop() break else: break else: ans.append(val) return ans
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
@@NeetCode No, else will not be nested into while. It is the Python while / else statement. If the condition meet, while will execute. If the condition doesn't meet, else will execute. However, if you break from while, it will not execute else but go to the next iteration. That's why he did continue in if condition (to see if a collision with the next ans[-1] and do break after elif (because both a and ans[-1] are gone, you can just check the next item in asteroids. It is a smart method but I think your version is more readable.
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 [1,1,1,1..........,1,-100], 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.
It's ok. This problem is tricky one. It seems very simple but the way all the pieces are connected is difficult to figure out. Either you know or not kind of thing. I guess.
Missing the explanation how you came to the stack use, ie. the thoughts before this.
Your explanation is extremely clear. Hope to have a colleague like you very much in the company.
See joint in leetcode.
What would you do if an asteroid comes from the right and joins a stable asteroid row?
It will keep colliding till the row becomes stable.
So first come will get affected.
Stack.
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
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 []
-2 and -1 are moving to the left. 1 and 2 are moving to the right. No collisions will happen, so no asteroids will explode. Therefore, the answer is same as the input [-2, -1, 1, 2]
I was also stuck on this. I feel it wasnt clear from the question that the order of the input mattered. I interpreted the question to ask to evaluate all *possible* collisions.
Yeah my dumb brain got confused on this test case too.. It's because we assumed that if the asteroid and the head of the stack have opposite directions, then they collide no matter what... however, that's not true because they only collide if the asteroid is moving to the left (negative) and the head of the stack is moving to the right (positive); otherwise, they will never collide
@@prasad9012 me too was stuck in the same test case 😂😂😂😂😂😂 this proves we all are human
This has got to be one of the cleanest solutions!
How did you come up the idea setting a=0 ?
does anyone know if there's a way to do it without modifying a and just using while/if statements?
@@hanyo3629 stack=[]
for i in asteroids:
while stack and i0:
#collision occured
if abs(i)>stack[-1]:
stack.pop()
continue
elif abs(i) == stack[-1]:
stack.pop()
break
else:
stack.append(i)
return stack
I think what youre calling diff is better named as "sum". So if the sum < 0, asteroid wins etc..
Thank you for your wonderful explanation
Great explanation
Thanks brother
Thank you for this explaniation!
Thanks for the amazing solution.
beautiful solution!
Nice explanation 🎉
Managed to came up with a stack solution but damn wish you could just reverse a stack in java and return :(
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.
Integer overflow exists*
Python: We don't do that here
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.
ok, nvm I thought about it more and I see why it is O(n). The total number of elements that ever go into the stack can be N since each element in the input list of size N can go into the stack once. So it'd be O(n) for iterating through the input array and O(n) total iterations through the stack over the course of the whole function, hence O(n) + O(n) = O(n). Leaving this here in case someone else wonders about this like I did
@@JK1836ey Nice explanation! I had the same question and your comment helped me figured it out.
@@JK1836ey Exactly because we are inserting an element in the stack once and only once we are removing the element(in case it is needed)
Amazing explanation !
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.
I think its because some how you're omitting negative asteroids; i made that mistake too. If 3 are going left(negative values), and one is going positive, then u got four asteroids that never collide. So the output IS the input.
Nice explanation. It would have been simpler if you added an else with while instead of making a = 0 and checking that condition later. Thanks anyway.
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
ans = []
k = 0
for val in asteroids:
while ans and val < 0 and ans[-1] > 0:
if ans[-1] + val < 0:
ans.pop()
elif ans[-1] + val == 0:
ans.pop()
break
else:
break
else:
ans.append(val)
return ans
For people coding in other languages like C++ and Java, please put the code in the description which will be really helpful
Made simple and easy👍
LeetCode has not explained this question properly, but NeetCode has 😂
Thank you brother
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
Should your else case be nested in the while loop, and if so why do we need the break statement?
@@NeetCode No, else will not be nested into while. It is the Python while / else statement. If the condition meet, while will execute. If the condition doesn't meet, else will execute. However, if you break from while, it will not execute else but go to the next iteration. That's why he did continue in if condition (to see if a collision with the next ans[-1] and do break after elif (because both a and ans[-1] are gone, you can just check the next item in asteroids. It is a smart method but I think your version is more readable.
U an Asteroid God
precise and clear
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 [1,1,1,1..........,1,-100], 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.
Nevermind, just red JK1836ey's response and that made a lot of sense. But i will keep my comment. Cheers.
Thanks man !!
thank u
I spent too much time on this problem and got stuck :(
It's ok. This problem is tricky one. It seems very simple but the way all the pieces are connected is difficult to figure out. Either you know or not kind of thing. I guess.
instead of 0 , i took the value -10001, rest, same to same
Is this a monotonically decreasing stack?
This is God stuff _/\_
vector asteroidCollision(vector& nums) {
int n = nums.size();
stack st;
for(int i=0;i 0){
int diff = nums[i] + st.top();
if(diff < 0){
st.pop();
}
else if(diff > 0){
nums[i] = 0;
}
else{
nums[i] = 0;
st.pop();
}
}
if(nums[i] != 0){
st.push(nums[i]);
}
}
vector ans;
while(!st.empty()){
ans.push_back(st.top());
st.pop();
}
reverse(ans.begin(),ans.end());
return ans;
}
This question was asked to me today in my interview and i messed up
was it faang or an oil company. I'm new sorry
Not faang
can someone please write the cpp code for the same ....?
I hate this fucking problem soo many edge cases
Bhai itna shi smjhate ho TH-cam pe kyu nhi pdaye😅
Thank you for the great explanation