Asteroid Collision


  • 0

    Click here to see the full article post


  • 0

    Just a variation, using sentinel -1 to avoid the constant ans and checks, and shortening/simplifying the inner code a bit:

    def asteroidCollision(self, asteroids):
        ans = [-1]
        for new in asteroids:
            while new < 0 < ans[-1]:
                if -new < ans[-1] or -new == ans.pop():
                    break
            else:
                ans.append(new)
        return ans[1:]
    

    Nice... we use "break" when the new asteroid "breaks" :-)


  • 0

    And shortening the Java one as well:

    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack();
      asteroids:
        for (int ast: asteroids) {
            while (!stack.isEmpty() && ast < 0 && 0 < stack.peek())
                if (-ast < stack.peek() || -ast == stack.pop())
                    continue asteroids;
            stack.push(ast);
        }
        return stack.stream().mapToInt(i->i).toArray();
    }

  • 0
    S

    When do say collision: {...}, what is that called? For example, is that defining a method within a method?


  • 0
    R

    @stong2351, it means break to outer loop, you can read it as "goto"


  • 0
    H

    Why stack is a better solution?
    2 pointer have the same time complexity with constant space complexity (of course we need to output an array, but if we change this problem to return a size and check modified original array as result, this space complexity is not necessary at all.)
    public int[] asteroidCollision(int[] asteroids) {
    int i, j;
    for(i = j = 0; i < asteroids.length; i ++){
    for(; j > 0 && asteroids[j - 1] > 0 && asteroids[j - 1] < -asteroids[i]; j --);
    if(j == 0 || asteroids[i] > 0 || asteroids[j - 1] < 0){
    asteroids[j ++] = asteroids[i];
    }else if(asteroids[i] == -asteroids[j - 1]) {
    j --;
    }
    }
    return Arrays.copyOf(asteroids, j);
    }


  • 0
    D

    @stong2351 This.. i don't know what he did there


  • 0
    K

    I also thought about a stack for the solution to this problem.
    I agree this is the perfect situation for the stack
    However, I just don't understand your thinking process, maybe because deep inside my mind, the stack is a vertically represented container... No right to left, but rather top bottom...


  • 0
    I

    I wrote the stack solution as well which was accepted. I was also thinking of Divide and Conquer where we find the largest magnitude element, recursively process left and right part then depending on the selected elements sign, either consume some elements from the left processed or right processed array. Wondering if someone has implemented it this way and got Accepted.


  • 0
    A

    Hi, I think there is a typo when building stack, top should be starting from the "leftmost" element instead of the "rightmost", is that correct?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.