---
tags: leetcode
---

# [735. Asteroid Collision](https://leetcode.com/problems/asteroid-collision/)
---
# My Solution
## The Key Idea for Solving This Coding Question
Monotonic stack
## C++ Code

class Solution {
public: 
    vector<int> asteroidCollision(vector<int> &asteroids) {
        vector<int> answer;

        for (auto &asteroid : asteroids) {
            if (answer.empty()) {
                answer.push_back(asteroid);
                continue;
            }

            if (asteroid > 0) {
                answer.push_back(asteroid);
                continue;
            }
            // asteroid < 0 is true

            if (answer.back() > 0 ) {
                // answer.back() and asteroid will collide.

                if (answer.back() > -asteroid) {
                    // asteroid explode.
                } else if (answer.back() == -asteroid) {
                    // Both exolode.
                    answer.pop_back();
                } else {
                    // answer.back() < -asteroid is true
                    // answer.back() explode.
                    while (!answer.empty() && answer.back() > 0 && 
                           answer.back() < -asteroid) {
                        answer.pop_back();
                    }

                    if (answer.empty()) {
                        answer.push_back(asteroid);
                        continue;
                    }
                    if (answer.back() < 0) {
                        answer.push_back(asteroid);
                        continue;
                    }
                    if (answer.back() > -asteroid) {
                        continue;
                    }
                    if (answer.back() == -asteroid) {
                        answer.pop_back();
                    }
                }
            } else {
                // answer.back() < 0
                answer.push_back(asteroid);
            }
        }

        return answer;
    }
};

## Time Complexity
$O(n)$
$n$ is the length of `asteroids`.
## Space Complexity
$O(n)$
$n$ is the length of `asteroids`.
# Miscellaneous
<!--
# Test Cases

[5,10,-5]

[8,-8]

[10,2,-5]

[-2,-1,1,2]

[10,2,-20]

* Wrong Answer:

[-2,1,1,-1]

* Runtime Error:

[1,-1,-2,-2]

* Wrong Answer:

[-2,-2,1,-2]

-->