735.asteroid-collision.md

735. Asteroid Collision

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

Simulation

We iterate all elements, and we only have to handle the case <- (go left), we start to check all the previous elements. To check with the previous elements, we can use a stack to store the elements, and we only deal withe the case previous is -> and current is <-:

• Previous > Current: The current will be destroyed, then we go to the next element.
• Previous == Current: Both elements will be destroyed, then we go to the next element.
• Previous < Current: The previous will be destroyed, we keep checking the previous elements until there is no element to compare.

fun asteroidCollision(asteroids: IntArray): IntArray {
    // 30, -40
    // -5, -10
    // -5, 10
    val stack = Stack<Int>()
    for (i in 0 until asteroids.size) {
        val right = asteroids[i]
        var existInFinal = true
        // For `-> <-` cases, we start to compare with the previous elements
        while (stack.isNotEmpty() && stack.peek() > 0 && right < 0) {
            val left = stack.peek()
            // Previous is greater than current
            if (left + right > 0) {
                existInFinal = false
                break
            } else if (left + right == 0) {
                existInFinal = false
                // Previous is destroyed
                stack.pop()
                break
            } else {
                stack.pop()
            }
        }
        if (existInFinal) {
            stack.push(right)
        }
    }
    return stack.toIntArray()
}

// Or we can store the results directly with Linked List
fun asteroidCollision(asteroids: IntArray): IntArray {
    val results = LinkedList<Int>()
    for (i in 0 until asteroids.size) {
        if (asteroids[i] > 0) {
            results.addLast(asteroids[i])
        } else {
            if (results.isEmpty() || (results.isNotEmpty() && results.last() < 0)) {
                results.addLast(asteroids[i])
            } else {
                while (results.isNotEmpty() && results.last() > 0) {
                    val left = abs(results.last())
                    val right = abs(asteroids[i])
                    if (left > right) {
                        break
                    } else if (left < right) {
                        results.removeLast()

                        // Remember to add this right if there is nothing to compare.
                        if (results.isEmpty() || (results.isNotEmpty() && results.last() < 0)) {
                            results.addLast(asteroids[i])
                        }
                    } else {
                        results.removeLast()
                        break
                    }
                }
            }
        }
    }
    return results.toIntArray()
}