movingAstroids.java

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        var len = asteroids.length;
        var stk = new ArrayList<Integer>();
        for (int cur : asteroids){
            if (Objects.nonNull(peek(stk)) && isPositiveNegative(peek(stk), cur)){
                if ((peek(stk) + cur) == 0){
                    pop(stk);
                } else if ((peek(stk) + cur) < 0){
                    while(
                        (Objects.nonNull(peek(stk))) && (isPositiveNegative(peek(stk), cur)) &&
                        ((peek(stk) + cur) < 0)
                    ){
                        pop(stk);
                    }
                    if (Objects.nonNull(peek(stk)) && isPositiveNegative(peek(stk), cur) && (peek(stk) + cur) == 0){
                        pop(stk);
                    } else if (Objects.isNull(peek(stk)) || !isPositiveNegative(peek(stk), cur)){
                        stk.add(cur);
                    }
                }
            } else {
                stk.add(cur);
            }
        }
        return toArray(stk);
    }

    private Integer peek(List<Integer> stk){
        Integer retVal = null;
        if (stk.size() != 0){
            retVal = stk.get(stk.size() - 1);
        }
        return retVal;
    }

    private void pop(List<Integer> stk){
        if (stk.size() != 0){
            stk.remove(stk.size() - 1);
        }
    }

    private int[] toArray(List<Integer> stk){
        var retVal = new int[stk.size()];
        for (int i = 0; i < stk.size(); i++){
            retVal[i] = stk.get(i);
        }
        return retVal;
    } 

    private boolean isPositiveNegative(Integer top, Integer cur){
        if (Objects.nonNull(top)){
            return (
                (top > 0) && (cur < 0)
            );
        }
        return false;
    }

}

LeetCode Question

Link: https://leetcode.com/problems/asteroid-collision/?envType=study-plan-v2&envId=leetcode-75

Achievement

• I have written the above code.
• The above solution uses stack implementation using List.
• The above code beats 64% of the total submissions regarding runtime with the value of 6ms.

Yet Another Better Solution

• During my past leetcode questions, I have observed that array manipulation if possible gives the best runtime compared to solutions implementing anything else.
  The below solution also is done by manipulating the array.

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        var len = asteroids.length;
        var loggedIn = 0;
        for (int i = 0; i < len; i++){
            var cur = asteroids[i];
            while(
                (loggedIn > 0) &&
                isPositiveNegative(asteroids[loggedIn - 1], cur) &&
                ((asteroids[loggedIn -1] + cur) < 0)
            ){
                loggedIn--;
            }

            if (
                (loggedIn == 0) ||
                (asteroids[loggedIn -1] < 0) ||
                cur > 0
            ){
                asteroids[loggedIn++] = cur;
            } else if ((asteroids[loggedIn - 1] + cur) == 0){
                loggedIn--;
            }
        }
        var retVal = new int[loggedIn];
        System.arraycopy(asteroids, 0, retVal, 0 , loggedIn);
        return retVal;
    }

    private boolean isPositiveNegative(int prev, int cur){
        return (
            (prev > 0) && (cur < 0)
        );
    }

}