LeetCode 735: Asteroid Collisions in JavaScript
As I’ve been job hunting, I’ve been attempting, studying, and learning from various LeetCode problems. I try an “Easy” problem or two to get me warmed up. Well, that and a cup of coffee.
Then I take a stab at a couple of “Medium” problems. Today we’ll be reviewing LeetCode 735: Asteroid Collision.
If you’re not familiar with this question, here is the full question:
Essentially, given an array of integers, we want to return an array of asteroids, after all the collisions have occurred. Each asteroid’s absolute value indicates its size and the sign represents the direction (positive going to the right, and negative moving left). A collision occurs when items are moving in opposite directions. The asteroid that goes *poof*? That’s the smaller value (after absolute value as been taken!) If the values are the same, they both explode. For the sake of argument, there’s no change in speed for each asteroid. Sound clear? If not, that’s okay, we’ll go through some examples to start getting a feel of the right steps to take.
Example Walkthroughs
Example 1:
Input: [5,10,-5]
Output: [5,10]Why? Items moving in the same direction don’t collide, so 5 and 10 are okay to keep. We get a sign change at -5. Since it’s moving in the opposite direction to 10, we have a collision! Signs only indicate the direction, so taking the absolute value of -5 and 10, gives us 5 and 10. The smaller asteroid is 5 so that one explodes. Leaving us with the final result of [5, 10].Example 2:
Input: [10,2,-5]
Output: [10]Why? Similarly here, 10 and 2 are both positive, so no collision. There’s a collision, however, between 2 and -5. The absolute value of the two elements gives 2 and 5. So the asteroid with the value of 2 is the one that explodes! Leaving us [10, -5]. But looks like we can have yet another collision. Taking the absolute value of both gives 10 and 5, and 5 explodes, leaving us with a final result of just [10]!
It’s important to note here: after we’ve calculated a collision and removed an asteroid, we can have another collision immediately following it! This will be important later, in our code.
And finally here’s an example of if both values are the same, but the signs are opposite:
Example 3:
Input: [8, -8]
Output: []Why? The output is an empty array, [], because the absolute value of both elements are the same! They’re also moving in opposite directions, so they both cancel each other out perfectly.
Pseudo Code
It always helps me to write out some pseudocode in the beginning. A helpful tip for me is to write my pseudocode using plain English, and avoiding getting too technical (i.e. adding variable names and rampant i’s).
Before I started writing my pseudo code though, I knew there were several important things to note from this problem:
- Collisions only happen on a sign change, specifically a positive to negative change.
- Collisions can occur one after another. I’ll refer to these as consecutive collisions.
I’ll be honest here, my immediate thought, was to loop from the last item of the array to the front. That way, handling consecutive collisions would simply be continuing the loop to the front. But, then I thought of another way — using a stack to keep track of the asteroids I have already checked. As I confirm asteroids, I’ll add them to the stack, and compare the current to the last item of the stack. If the last item of the stack is the one that loses in the collision, I’d simply pop it off! A pretty solid way to try, so here’s what I wrote down as my pseudo code notes:
- Loop through the array.
- Check if a collision is possible (current value is negative, and the previous item is positive).
- If a collision is possible, compare the absolute value of both elements.
- If the current value is smaller, don’t add it to the stack, and remove the previous item from the stack.
- If the current value is equal to the previous value, don’t add it to the stack.
- If the current value is bigger, remove the previous item from the stack, and add the current value to the stack.
- Do the above in a while loop because collisions can occur one after another.
- If collision not possible, add the item to the stack.
- Return stack.
Code, Code, Code
If you’re super eager to find the entire solution, check out the gist here!
We’ll first begin by initializing a stack, which is an empty array. We know we plan to return the stack, and that we also plan to loop through the array. Here’s our beginning setup. We can check number 1 off our pseudo code list.
Now we’re going to check if a collision is possible. A collision is possible if the current asteroid is moving to the left, and the previous asteroid is moving to the right.
I’m going to use a variable, called add, to indicate when we should add the value to the stack. If add is false, it shouldn’t be added to the stack, and if add is true, it should be added to the stack.
Parts 4, 5, and 6 from the pseudocode list are all potential scenarios for calculating collisions. Let’s fill out our potential solutions in an if/else-if/else statement.
If the current asteroid is greater than the previous asteroid, this means the previous asteroid explodes, and we need to remove it from the stack. This also means we need to add the current asteroid to the stack, so we leave the variable add set to true. Because it’s true, we’ll push it onto the stack, as written on line 18.
If the current asteroid and the previous asteroid are equal in value, then we don’t want either of them! We’ll remove the previous asteroid, and we’ll set add to false, so we don’t add it.
If the current asteroid is smaller than the previous asteroid, then we toggle add to false so that we don’t add it either, and leave the previous asteroid be.
Our function, as it is, will check for collisions and will add them or remove from the stack, but it won’t calculate consecutive collisions- collisions happening one after another.
I made a note in my pseudocode to include a while loop to allow for consecutive collisions. A while loop is better suited here because we don’t know how many times we’ll have to continuously evaluate our previous asteroid for more collisions.
The while loop should be inside of our first if-else statement, where we’ve already evaluated the current value to be negative, and the previous stack to be positive. We want the nested if/else-if/else block to execute multiple times until we stop finding a negative previous value. The while loop should occur if the last item in the stack is positive (maintaining our sign change condition!) and if there are items in the stack.
So here’s how I implemented the while loop.
But it didn’t work! I got a time exceeded error, which meant I wasn’t breaking out of my while loop when I should.. can you spot the missing piece? Took me some time to find it myself!
You can spot the missing piece on line 17. If we ever got to a point where add = false, meaning we shouldn’t add it, there’s no point in continuing. We want to break out of the loop!
There you have it, folks! Hopefully, this walkthrough helped explain some nuances of the problem, and it makes more sense to you. Feel free to leave a comment or find me on Twitter, if you have a question or just want to chat!
