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


Log in to reply
 

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