Kotlin Stack using an ArrayList to compare and remove elements

Question

Is this a performant strategy to implement a stack in Kotlin to compare and delete values?

Expect

Create a stack in order to compare an array of asteroids (ASTs) and handle collisions (deletions), returning the final array of ASTs after collisions.

• Each AST moves at the same speed
• Negative numbers move left, positive numbers move right
• Smaller ASTs explode (are deleted), the same size both explode, and same direction ASTs do nothing

See: LeetCode

Example 1:
Input: asteroids = [5, 10, -5]
Output: [5, 10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

ArrayList Stack Strategy

Create a stack using an ArrayList to compare asteroid (AST) direction, values, and remove ASTs.

The solution performs as expected in terms of achieving the correct results. However, I'm looking to improve speed and memory performance.

See: GitHub repository

1. Build ArrayList used as a stack and add the AST values to the stack
2. Start curIndex at the top of the stack and check the stack until curIndex is at the second element of the stack, thus checking for all possible AST collisions.
3. Using the current cur and previous prev values, check whether a collision will occur. A collision occurs when prev is positive and cur is negative.
4. Given a collision with ASTs with equal value, remove both ASTs. If the curIndex is not at the end of the stack after removing ASTs, continue to check for right-most collisions by decrementing curIndex--. Otherwise, fully decrement curIndex-=2
5. Given a collision with one AST with a larger value, remove the smaller AST. Only decrement when curIndex is at the end of the stack.
6. If there are no collisions, decrement the stack curIndex--.

Implement

fun asteroidCollision(asteroids: IntArray): IntArray {
 val stack = ArrayList<Int>()
 for (a in asteroids) stack.add(a)
 var curIndex = stack.size - 1
 while (curIndex >= 1) {
 val cur = stack.get(curIndex)
 val prev = stack.get(curIndex - 1)
 if (prev.isRight() && cur.isLeft()) {
 if (Math.abs(cur) == Math.abs(prev)) {
 stack.removeAt(curIndex)
 stack.removeAt(curIndex - 1)
 if (curIndex - 2 == stack.size - 1)
 curIndex -= 2
 else curIndex--
 } else if (Math.abs(prev) > Math.abs(cur)) {
 stack.removeAt(curIndex)
 if (curIndex - 1 == stack.size - 1)
 curIndex--
 } else {
 stack.removeAt(curIndex - 1)
 curIndex--
 }
 } else curIndex--
 }
 return stack.toIntArray()
}
fun Int.isLeft() = this < 0
fun Int.isRight() = this > 0

Potential improvement

This seems like it could be a potential improvement. However, it still requires creating a new data structure vs. working with the original array and requires converting the data structure back into an array to return the results.

1. Build a double LinkedList class.
2. Pass in one element at a time.
3. Check the top/last element to see if it collides with the previous element.
4. Continue to check previous elements after all of the original elements are added.

• Reinderien: We cannot comment on a broad notion of "what is the best strategy", but we can comment on whether the implementation that you have shown is a good one. I'm going to nudge your title in that direction.

Answer 1

An array to list can be done by the function toList().
list.size-1 is an existing property on a list called lastIndex.

'Math.abs' is from Java. Kotlin has its own abs, which isn't prefixed by a class.

List provides an operator function to access by index: stack.get(curIndex) can be written as stack[curIndex]

fun asteroidCollision(asteroids: IntArray): IntArray {
 val stack = asteroids.toMutableList()
 var curIndex = stack.lastIndex
 while (curIndex >= 1) {
 val cur = stack[curIndex]
 val prev = stack[curIndex - 1]
 if (prev.isRight() && cur.isLeft()) {
 if (abs(cur) == abs(prev)) {
 stack.removeAt(curIndex)
 stack.removeAt(curIndex - 1)
 if (curIndex - 2 == stack.lastIndex)
 curIndex -= 2
 else curIndex--
 } else if (abs(prev) > abs(cur)) {
 stack.removeAt(curIndex)
 if (curIndex - 1 == stack.lastIndex)
 curIndex--
 } else {
 stack.removeAt(curIndex - 1)
 curIndex--
 }
 } else curIndex--
 }
 return stack.toIntArray()
}

flow

The if-else if-else chain can be reduced to two if-statements.
This is because the case where the absolute value of cur and prev are the same is just the other two cases combined.
As far as I know, you do need more variables, to make it possible. Therefor, this is just another choice, with its own drawbacks:

fun asteroidCollision(asteroids: IntArray): IntArray {
 val stack = asteroids.toMutableList()
 var index = stack.lastIndex
 while (index >= 1) {
 val curIndex = index
 val cur = stack[curIndex]
 val prevIndex = index-1
 val prev = stack[prevIndex]
 if (prev.isRight() && cur.isLeft()) {
 if (abs(prev) >= abs(cur)){
 stack.removeAt(curIndex)
 if (index-1==stack.lastIndex)
 index--
 }
 if (abs(cur) <= abs(prev)){
 stack.removeAt(prevIndex)
 index--
 }
 } else index--
 }
 return stack.toIntArray()
}