Skip to content

Instantly share code, notes, and snippets.

@ritik-agrawal
Created February 13, 2024 07:04
Show Gist options
  • Save ritik-agrawal/0f00f1feaca2f754a669772f2ea750c8 to your computer and use it in GitHub Desktop.
Save ritik-agrawal/0f00f1feaca2f754a669772f2ea750c8 to your computer and use it in GitHub Desktop.
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;
}
}
@ritik-agrawal
Copy link
Author

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

}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment