Asteroid Collision (opens in a new tab)
- Start from left of the array, if the asteroid is positive, push it to the stack
- If the asteroid is negative, keep popping from the stack until the stack is empty or the top of the stack is positive
/**
* @param {number[]} asteroids
* @return {number[]}
*/
var asteroidCollision = function (asteroids) {
const left = [], right = [];
for (const asteroid of asteroids) {
// when a right moving asteroid comes
if (asteroid > 0) {
left.push(asteroid);
continue;
}
// when left moving asteroid destroys the possible right moving asteroids
while (left.length && left.at(-1) < -asteroid) {
left.pop();
}
// for the remaining right moving asteroid (may be equal or greater than the left moving destroyer)
if (left.length) {
if (left.at(-1) === -asteroid) {
left.pop();
}
continue;
}
// if left moving asteroid wins
right.push(asteroid);
}
return right.concat(left);
};Complexity
- Time: O(n)
- Space: O(n)
Validate Stack Sequences (opens in a new tab)
- Create a stack and loop through the pushed elements
- If the element popped is encountered loop through the array popped and find the point where it is not equal
/**
* @param {int[] , int[]} pushed, popped
* @return {boolean}
*/
public boolean validateStackSequences(int[] pushed, int[] popped) {
// start from pushed and check if it is in popped
// just follow the instructions, if not encpuntered just return false
int pop =0;
Stack<Integer> stack = new Stack<>();
for(int i=0; i<pushed.length ; i++) {
stack.add(pushed[i]);
if(pushed[i]==popped[pop]) {
for(int j=pop ; j<popped.length; j++) {
if(!stack.isEmpty() && stack.peek()==popped[j]){
pop++;
stack.pop();
} else {
break;
}
}
}
}
return stack.isEmpty();
}Complexity
- Time: O(n)
- Space: O(n)