Find problem link, notes under Step 9: takeuforward.o... Follow me on socials: linktr.ee/take...
Пікірлер: 44
@ugthesep5706Ай бұрын
solved by my own in around 33 minutes. Was confused at the starting like how are the collision happening then read the description carefully and i got it
@subhajitdey135Ай бұрын
Same
@avengergirl_046428 күн бұрын
Then provide code
@subhajitdey13528 күн бұрын
@@avengergirl_0464 vector asteroidCollision(int N, vector &arr) { // code here stackst; int n=N; for(int i=0;i=0 || (st.top()0)) st.push(arr[i]); else{ while(!st.empty() && st.top()>0 && arr[i]
@ugthesep570628 күн бұрын
@@avengergirl_0464 class Solution { public: vector asteroidCollision(vector& asteroids) { stack st; for(int i=0;i0 and asteroids[i]=top and top>0 and !st.empty()){ if(top==absval){ st.pop(); break; } st.pop(); if(!st.empty()) top = st.top(); } if(top!=absval and (asteroids[i]top)) st.push(asteroids[i]); } else st.push(asteroids[i]); } } vector res(st.size()); for(int i=res.size()-1;i>=0;i--){ res[i] = st.top(); st.pop(); } return res; } };
no need to reverse the stack ,we have to return an array as answer , so we can get the stack size , create an array of that size and pop and directly start inserting into the array from backward direction(last index).
@akshitrajputhere10 күн бұрын
Damn! Good observation
@randomshorts52006 күн бұрын
that will take O(stack size) time, just use vector as stack.
@akshitrajputhere5 күн бұрын
@@randomshorts5200 but is it a good practice?
@hashtagccАй бұрын
these type of question the bruteforce solution is the difficult one
@rohanbera6227Ай бұрын
This is only for my understanding pls ignore. Each asteroid is travelling at same speed. We are traversing from left to right in an array so if asteroid travelling from left to right it means it would not collide at that particular of timeframe which is kind of equivalent to the index of an array and if asteroid is coming from right to left it would collide because we are traversing from left to right (if there ) So we need to take negative number into consideration at that time and see if any asteroid is coming from left to right and if it is coming then it collides but once the asteroid collides (which was coming from right to left) it exits our timeframe. eg :- -2, -1, 1, 2 -2 at index 0 comes from right to left it should collide but there is no asteroid coming from left so nothing collides -> -3 -1 at index 1 comes from right to left it should collide but there is no asteroid coming from left so no collision -> -2 1 at index 2 going from left to right it shouldn't collide because we are travelling from left to right -> 1 -> +1 2 at index 3 doesn't collide -> +2
00:04 Solving the problem of asteroid collisions in the given array. 02:20 Illustrates asteroid collisions and elimination process. 04:29 Using stack data structure to track element traversal 06:35 Asteroid collisions simulation using stack data structure 08:42 Using stack or list in asteroid collisions 10:47 Demonstration of asteroid collisions in a stack 12:59 Handling asteroid collisions using stack and queue 15:29 Explaining time and space complexity
@cyanideyt957923 күн бұрын
Java Solution TC : O(2N), O(N) for traversing and another O(N) for pushing and popping at max 'N' elements onto the stack. SC : O(2N), O(N) is for using external list data structure and another O(N) for converting the list into array to return the answer. class Solution { public int[] asteroidCollision(int[] asteroids) { // List to store the resulting asteroids after collisions List list = new ArrayList(); // Loop through each asteroid in the array for (int i = 0; i < asteroids.length; i++) { // If the current asteroid is moving to the right (positive direction) if (asteroids[i] > 0) { // Add it directly to the list (no collision with left-moving asteroids) list.add(asteroids[i]); } // If the current asteroid is moving to the left (negative direction) else { // Check for collisions with right-moving asteroids in the list while (!list.isEmpty() && list.get(list.size() - 1) > 0 && list.get(list.size() - 1) < Math.abs(asteroids[i])) { // Remove the smaller right-moving asteroid since it collides and explodes list.remove(list.size() - 1); } // If the list is empty or the last asteroid in the list is also moving to the left, // or there are no more right-moving asteroids to collide with if (list.isEmpty() || list.get(list.size() - 1) < 0) { // Add the current left-moving asteroid to the list list.add(asteroids[i]); } // If the last asteroid in the list is the same size but moving in the opposite direction else if (list.get(list.size() - 1) == Math.abs(asteroids[i])) { // Both asteroids destroy each other (equal in magnitude), so remove the last one list.remove(list.size() - 1); } // If the current left-moving asteroid is smaller, it is destroyed by the larger right-moving asteroid, // and we do not add it to the list (handled implicitly by not adding it to the list). } } // Convert the List of remaining asteroids to an array to return as the result int[] result = new int[list.size()]; for (int i = 0; i < list.size(); i++) { result[i] = list.get(i); } return result; } }
@Cubeone117 күн бұрын
i figured out the solution in just 5 minutes, pretty easy question if you could figure out that you have to use a stack.
@SibiRanganathL22 күн бұрын
Understood 👍
@mauryaToonsАй бұрын
We have to add one more condition in the last els if, and that is when the list.back()
@valendradangi1822Ай бұрын
this condition is written in else block therefore arr[i] is already < 0 why are you checking it again? so (st.empty || st.back() < 0) will suffice.
@aryansingh66512 сағат бұрын
Most of the time i got the idea whats happening and solve it through brute force but unable to optimize it may be 3-4 out of 10 time able to do so.
@akshaysingh23521 күн бұрын
class Solution { public: vector asteroidCollision(vector& asteroids) { stack st; for(int i = 0; i < asteroids.size(); i++) { bool flag = false; while(!st.empty() && asteroids[i] < 0 && st.top() > 0) { if (abs(asteroids[i]) > abs(st.top())) { st.pop(); } else if (abs(asteroids[i]) == abs(st.top())) { st.pop(); flag = true; break; } else { flag = true; break; } } if (!flag) { st.push(asteroids[i]); } } vector ans; while (!st.empty()) { ans.insert(ans.begin(), st.top()); st.pop(); } return ans; } };
@subee128Ай бұрын
Thanks
@AyushRaj-rr1hcАй бұрын
I have doubt with input -2 -1 1 2, what would be the output in leetcode expected output is the same as input
@AbhishekGupta-zf2swАй бұрын
Yes, as 1st two move in left (stack is empty so push) and then rest of the element are moving right, opposite direction, therefore no collision
@omkarshendge5438Ай бұрын
@@AbhishekGupta-zf2sw yup this!
@DrawwithNaviАй бұрын
solved this without watching the video in 15 mins in o(n) w
@15anshulkumarАй бұрын
You are so talented bro
@Rahul-kw6zf9 күн бұрын
chaalak bro
@Shivi3259029 күн бұрын
understood
@saketjaiswal34316 күн бұрын
koi check karke batao na kya error hai isme. test cases pass nahi ho rahe class Solution { public: vector asteroidCollision(vector& asteroids) { vector st; int n = asteroids.size(); for(int i = 0; i0) st.push_back(asteroids[i]); else{ while(!st.empty() && st.back()>0 && st.back()
@umeshchauhan3877Ай бұрын
😊
@steveservantАй бұрын
class Solution { public int[] asteroidCollision(int[] asteroids) { Stack stack = new Stack(); for(int i=0;i0){ stack.push(asteroids[i]); } else { while(!stack.isEmpty()){ int top = stack.peek(); if(top=0;i--){ ansArray[i] = stack.pop(); } return ansArray; } } //
@himanshugupta8430Ай бұрын
can you explain in this case [-19,-18, 20] Why is the answer [-19,-18, 20] and not [20].
@sripooja2802Ай бұрын
Bcoz, 1st 2 elements are moving to the left and the last element is moving to the right. So they won't collide
@sai-cz9lm23 күн бұрын
because -19 is going left and 20 is going right so they can never collide
@samiranroyy170018 күн бұрын
class Solution { public int[] asteroidCollision(int[] asteroids) { int n = asteroids.length; Stack st = new Stack(); for(int i=0;i0) { st.push(asteroids[i]); }else{ while(!st.isEmpty() && st.peek()>0 && st.peek()
@subhajitdey135Ай бұрын
C++ solution with stack : vector asteroidCollision(int N, vector &arr) { // code here stackst; int n=N; for(int i=0;i=0 || (st.top()0)) st.push(arr[i]); else{ while(!st.empty() && st.top()>0 && arr[i]
@rajitpal9274Ай бұрын
what's the code of 3:05 (when -3 is getting eliminated) anyone please??
@no_131311 күн бұрын
Cz there is 7 before which is a positive and greater than absolute of -3 i.e 3