L11. Aestroid Collisions | Stack and Queue Playlist

Поділитися
Вставка
  • Опубліковано 22 гру 2024

КОМЕНТАРІ • 68

  • @prathamsharma5190
    @prathamsharma5190 2 місяці тому +22

    the first question that i made by myself without any help, getting more confidence day by day!!!!

  • @Akash-Bisariya
    @Akash-Bisariya 3 місяці тому +5

    08:43 is very important to understand for an assumption that we need to insert everytime there is a positive element in array.

    • @Rohan-cn4ji
      @Rohan-cn4ji Місяць тому +1

      thank you so much i literally was confused for straight up hours

  • @agrawalmitesh4395
    @agrawalmitesh4395 4 місяці тому +18

    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).

  • @ugthesep5706
    @ugthesep5706 5 місяців тому +23

    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
      @subhajitdey135 4 місяці тому

      Same

    • @avengergirl_0464
      @avengergirl_0464 4 місяці тому

      Then provide code

    • @subhajitdey135
      @subhajitdey135 4 місяці тому

      @@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]

    • @ugthesep5706
      @ugthesep5706 4 місяці тому

      @@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;
      }
      };

    • @MrBro-z7d
      @MrBro-z7d 4 місяці тому

      @@avengergirl_0464
      class Solution {
      public:
      vector asteroidCollision(vector& asteroids) {
      vector ans;
      int n=asteroids.size();
      stack stk;
      stk.push(asteroids[0]);
      for(int i=1;i0) stk.push(asteroids[i]);
      else
      {
      while (!stk.empty() && stk.top() > 0 && stk.top() < abs(asteroids[i]))
      {
      stk.pop();
      }
      if(!stk.empty() && asteroids[i]

  • @babulalyadav4305
    @babulalyadav4305 5 місяців тому +1

    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

  • @rohanbera6227
    @rohanbera6227 4 місяці тому +4

    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

  • @hashtagcc
    @hashtagcc 5 місяців тому +10

    these type of question the bruteforce solution is the difficult one

  • @Cubeone11
    @Cubeone11 3 місяці тому +4

    i figured out the solution in just 5 minutes, pretty easy question if you could figure out that you have to use a stack.

  • @mauryaToons
    @mauryaToons 4 місяці тому +6

    We have to add one more condition in the last els if, and that is when the
    list.back()

    • @valendradangi1822
      @valendradangi1822 4 місяці тому +1

      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.

    • @aaryansj8016
      @aaryansj8016 23 дні тому

      Yep this will require

  • @sahilmujawar8217
    @sahilmujawar8217 Місяць тому

    great explanation bhaiya

  • @UECAshutoshKumar
    @UECAshutoshKumar 3 місяці тому +1

    Thank you

  • @aryansingh665
    @aryansingh665 3 місяці тому +1

    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.

  • @AyushRaj-rr1hc
    @AyushRaj-rr1hc 5 місяців тому +4

    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
      @AbhishekGupta-zf2sw 5 місяців тому +2

      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
      @omkarshendge5438 4 місяці тому

      @@AbhishekGupta-zf2sw yup this!

    • @aryasharma69
      @aryasharma69 2 місяці тому

      everything will get added in the stack

  • @akshaysingh235
    @akshaysingh235 4 місяці тому +1

    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;

    }
    };

  • @apmotivationakashparmar722
    @apmotivationakashparmar722 3 місяці тому

    Thank you so much !

  • @rishi.vakharia
    @rishi.vakharia Місяць тому

    def sign(num):
    return num//abs(num)
    def asteroidCollision(arr):
    n = len(arr)
    i = 0
    lst = []
    while(i < n):
    # will process asteroid i
    if len(lst) > 0 and lst[-1] > 0 and arr[i] < 0:
    # collision will happen
    if abs(lst[-1]) == abs(arr[i]): # tie
    lst.pop()
    i += 1
    elif abs(lst[-1]) > abs(arr[i]): # last wins
    i += 1
    else: # opp wins
    lst.pop()
    else:
    # no collision
    lst.append(arr[i])
    i += 1
    return lst
    print(asteroidCollision([-2,-1,1,2]))

  • @shreyxnsh.14
    @shreyxnsh.14 3 місяці тому

    CPP Code I came up with:
    class Solution {
    public:
    vector asteroidCollision(vector& asteroids) {
    stack st;
    for(const auto& it: asteroids){
    bool exploded = false;
    while(!(st.empty()) && it 0){
    if(abs(it) > abs(st.top())){
    st.pop();
    }else if(abs(it) == abs(st.top())){
    st.pop();
    exploded = true;
    break;
    }else{
    exploded = true;
    break;
    }
    }
    if(!exploded){
    st.push(it);
    }
    }
    vector ans(st.size());
    for(int i=st.size()-1;i>=0;i--){
    ans[i] = st.top();
    st.pop();
    }
    return ans;
    }
    };

    • @SoulFrmTitanic
      @SoulFrmTitanic 3 місяці тому

      bro thats a great one!! Can you just tell me what was the intuition behind this beautiful approach??
      Would be very helpful for me!! 🤝

    • @shreyxnsh.14
      @shreyxnsh.14 3 місяці тому

      @@SoulFrmTitanic i dont remember much, just thought to keep removing elements from stack until the current asteroid is destroyed (if the asteroid is weaker than the previous coz otherwise just remove the current asteroid and break out)

    • @SoulFrmTitanic
      @SoulFrmTitanic 3 місяці тому +1

      @@shreyxnsh.14 achaa , ok bhai

  • @SibiRanganathL
    @SibiRanganathL 4 місяці тому

    Understood 👍

  • @DrawwithNavi
    @DrawwithNavi 5 місяців тому +4

    solved this without watching the video in 15 mins in o(n) w

  • @oyeshxrme
    @oyeshxrme 2 місяці тому

    thanks bhaiya

  • @steveservant
    @steveservant 4 місяці тому +1

    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;
    }
    }
    //

  • @DeadPoolx1712
    @DeadPoolx1712 2 місяці тому

    UNDERSTOOD;

  • @subee128
    @subee128 5 місяців тому

    Thanks

  • @subhajitdey135
    @subhajitdey135 4 місяці тому +2

    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]

  • @charchitagarwal589
    @charchitagarwal589 2 місяці тому +2

    The implementation is hard for this problem

  • @rutujashelke4208
    @rutujashelke4208 3 місяці тому

    Understood

  • @mathsworldbysuraj6278
    @mathsworldbysuraj6278 18 днів тому

    This is simple , TC - O(4N)~N , SC - O(2N)
    vector asteroidCollision(vector& asteroids) {
    int n=asteroids.size();
    stack st;
    vector nums;
    for(int i=0;i0 && valabs(top))
    val=val;
    else if(abs(val)

  • @samiranroyy1700
    @samiranroyy1700 4 місяці тому +1

    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()

  • @cyanideyt9579
    @cyanideyt9579 4 місяці тому +1

    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;
    }
    }

  • @ShauryaGoyal-y6g
    @ShauryaGoyal-y6g 3 місяці тому

    sir notes upload krdo site par

  • @Shivi32590
    @Shivi32590 4 місяці тому

    understood

  • @umeshchauhan3877
    @umeshchauhan3877 5 місяців тому +1

    😊

  • @rajitpal9274
    @rajitpal9274 4 місяці тому

    what's the code of 3:05 (when -3 is getting eliminated) anyone please??

    • @no_1313
      @no_1313 3 місяці тому

      Cz there is 7 before which is a positive and greater than absolute of -3 i.e 3

  • @saketjaiswal3431
    @saketjaiswal3431 3 місяці тому

    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()

  • @mathsworldbysuraj6278
    @mathsworldbysuraj6278 18 днів тому

    vector asteroidCollision(vector& asteroids) {
    int n=asteroids.size();
    stack st;
    vector nums;
    for(int i=0;i0 && valabs(top))
    val=val;
    else if(abs(val)

  • @himanshugupta8430
    @himanshugupta8430 4 місяці тому

    can you explain in this case [-19,-18, 20] Why is the answer [-19,-18, 20] and not [20].

    • @sripooja2802
      @sripooja2802 4 місяці тому +3

      Bcoz, 1st 2 elements are moving to the left and the last element is moving to the right. So they won't collide

    • @sai-cz9lm
      @sai-cz9lm 4 місяці тому

      because -19 is going left and 20 is going right so they can never collide

  • @abhinavabhi3568
    @abhinavabhi3568 8 днів тому

    Understood

  • @sujalthakkar2118
    @sujalthakkar2118 Місяць тому

    understood