DSA Interview Challenges

Asteroid Collision

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

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

Java


  /**
   * @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)