Posted on

## Submission 1

``````class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
stack<int> stk;

for (auto x: asteroids) {
if (stk.empty() || stk.top() < 0 || (stk.top() > 0 && x > 0)) {
stk.push(x);
continue;
}

while (!stk.empty()) {

auto y = stk.top(); // 1
if (y < 0 || (y > 0 && x > 0)) break; // y = 1, x = -2
// y > 0 && x < 0
if (y == -x) {
stk.pop();
break;
}

if (y < -x) {
stk.pop();
if (stk.empty() || stk.top() < 0)
stk.push(x);
continue;
}

if (y > -x) {
break;
}
}
}

vector<int> rets;

while(!stk.empty()) {
rets.push_back(stk.top());
stk.pop();
}

reverse(rets.begin(), rets.end());

return rets;
}
};

// -2 -2 1 -2``````

## Submission 2

``````class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
set<int> goRight;
set<int> goLeft;

for(size_t i = 0; i < asteroids.size(); ++i) {
if(asteroids[i] > 0) {
goRight.insert(i);
} else {
goLeft.insert(i);
}
}

int prevRightCnt = goRight.size(), prevLeftCnt = goLeft.size();
while(true) {

for(auto iterRight = goRight.begin(); iterRight != goRight.end(); ++iterRight) {
auto iterLeft = goLeft.upper_bound(*iterRight);
if (iterLeft == goLeft.end()) continue;
if (next(iterRight) != goRight.end() &&
*next(iterRight) < *(iterLeft)) continue;
auto x = *iterRight;
auto y = *iterLeft;
if (asteroids[x] <= -asteroids[y]) {
goRight.erase(x);
}
if (asteroids[x] >= -asteroids[y]) {
goLeft.erase(iterLeft);
}
break;
}

if (prevLeftCnt == goLeft.size() && prevRightCnt == goRight.size()) break;
prevRightCnt = goRight.size();
prevLeftCnt = goLeft.size();
}

vector<int> rets;

goRight.insert(goLeft.begin(), goLeft.end());

for(auto idx: goRight) {
rets.push_back(asteroids[idx]);
}

return rets;

}
};

// 1 1 -1

// 1 -1 -1 1 1 1 1 -1 1 1 1 -1 -1 -1 [1 1]

// goLeft 2
// goRight 0 1

// goLeft 0 1
// goRight 2``````