DSA-047 · FOCUSED PRACTICE
Asteroid Collision
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 22851 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the surviving asteroids in original left-to-right order after all collisions in the equal-speed line model.
- asteroids is non-null with 0–100,000 nonzero signed int values. Positive means right-moving, negative means left-moving, and magnitude is size. Both methods throw IllegalArgumentException for zero. Integer.MIN_VALUE is allowed and has magnitude 2147483648.
- Asteroids begin in input order at distinct positions and all have equal speed magnitude. Only a right-moving left asteroid and a left-moving right asteroid approach. The smaller size is destroyed; equal sizes destroy both; the larger continues unchanged.
- Return a new int[] of survivors in original order and preserve the source. Compare magnitudes in long, widening before negating a negative value. This simplified model does not cover arbitrary velocities, acceleration, or different collision physics.
Examples
Input:
[10,2,-5]
Output:[10]The incoming -5 destroys 2, then is destroyed by 10; one collision is not enough.
Input:
[-2,-1,1,2]
Output:[-2,-1,1,2]Same-direction neighbors and outward-moving opposite signs never approach.
Before you start
- Stack top versus bottom and last-in-first-out order
- Loop invariants, checked arithmetic, and amortized analysis
Recognize the structure
The processed prefix has a stable survivor sequence. A newly arriving left-moving asteroid can interact only with its rightmost right-moving survivor; destroying that survivor may expose another, so collision handling is a loop.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 153/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Which processed survivor would a new asteroid encounter first?
Hint 2
Can destroying one survivor expose another collision?
Hint 3
Loop only for positive-top/negative-incoming pairs and preserve the incoming liveness state.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Repeatedly resolve adjacent approaching pairs
Copy values into a list, locate the first positive-negative adjacent pair, remove the smaller or both on equality, and restart. For [10,2,-5], remove 2 to get [10,-5], then remove -5 to get [10]. Every collision removes an item, but rescans and list shifts yield O(n²) worst-case time.
Improve the baseline
Keep the stable prefix result
The stack holds survivors after all collisions within the processed prefix. Its top is the rightmost survivor.
Resolve only approaching directions
While incoming<0 and top>0, compare positive top size with -(long)incoming. Pop smaller tops and continue; on equal size pop the top and kill the incoming; on a larger top kill only the incoming.
Append an unblocked survivor
If the incoming remains alive, push it. At completion, iterate the deque bottom-to-top to return the original spatial order, rather than LIFO pop order.
Why it is correct
Stable-prefix invariant
After each completed input occurrence, the stack in bottom-to-top order is the stable collision result of that prefix, with no adjacent positive-negative pair left inside it.
Locality of the next collision
A positive incoming asteroid cannot meet anything to its left at equal speed. A negative incoming first meets only the rightmost positive survivor; any survivor before it is shielded until that top is destroyed. The comparison implements the size rule, and a surviving incoming repeats against the newly exposed top.
Completion and amortization
When the loop ends, either the incoming is gone or no approaching top remains, so pushing it restores stability. Every input is pushed at most once and popped at most once; collision work totals O(n). Final bottom-to-top iteration preserves survivor order.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
private static void validate(int[] asteroids) {
for (int value : asteroids) if (value == 0) throw new IllegalArgumentException("nonzero asteroids required");
}
public static int[] asteroidCollision(int[] asteroids) {
validate(asteroids);
ArrayDeque<Integer> survivors = new ArrayDeque<>();
for (int current : asteroids) {
boolean alive = true;
while (alive && current < 0 && !survivors.isEmpty() && survivors.peek() > 0) {
if ((long) survivors.peek() < -(long) current) survivors.pop();
else {
if ((long) survivors.peek() == -(long) current) survivors.pop();
alive = false;
}
}
if (alive) survivors.push(current);
}
int[] answer = new int[survivors.size()]; int write = 0;
for (var iterator = survivors.descendingIterator(); iterator.hasNext();) answer[write++] = iterator.next();
return answer;
}
public static int[] baseline(int[] asteroids) {
validate(asteroids);
List<Integer> remaining = new ArrayList<>(); for (int value : asteroids) remaining.add(value);
while (true) {
int i = 0;
while (i + 1 < remaining.size() && !(remaining.get(i) > 0 && remaining.get(i + 1) < 0)) i++;
if (i + 1 >= remaining.size()) break;
long left = remaining.get(i), right = -(long) remaining.get(i + 1);
if (left < right) remaining.remove(i);
else if (left > right) remaining.remove(i + 1);
else { remaining.remove(i + 1); remaining.remove(i); }
}
return remaining.stream().mapToInt(Integer::intValue).toArray();
}
}
Read the meaningful blocks
Widen before negating
-(long)Integer.MIN_VALUE is positive 2147483648. Negating as int first would overflow and invalidate the size comparison.
Track incoming liveness
Equality destroys both, so the incoming must not be pushed after popping an equal top.
Use a survivor array in spatial order
ArrayDeque push puts the rightmost survivor at its front; descendingIterator reads from the original leftmost survivor toward the right.
Complexity
O(n) total time including validation and final output, with O(n) survivor workspace and O(n) returned storage in the worst case.
The adjacent-reduction baseline uses O(n²) time and O(n) list/output storage. Small tests use a separate earliest-collision simulation based on original positions and equal-speed trajectories; the large cascade runs only through the optimized method.
Exact-state walkthroughs
Reveal normal and boundary traces
A cascade exposes a larger survivor
Input: [10,2,-5] · Result: [10]
Step 1 of 10: Start with the stable result of an empty prefix.
Survivors are displayed in spatial order, with the rightmost at the stack top.
- 0: 10
- 1: 2
- 2: -5
Empty at this step.
| Variable | Value |
|---|---|
| values | [10,2,-5] |
| survivorValues | [] |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[] asteroids) { 4 for (int value : asteroids) if (value == 0) throw new IllegalArgumentException("nonzero asteroids required"); 5 } 6 public static int[] asteroidCollision(int[] asteroids) { 7 validate(asteroids); 8 ArrayDeque<Integer> survivors = new ArrayDeque<>(); 9 for (int current : asteroids) { 10 boolean alive = true; 11 while (alive && current < 0 && !survivors.isEmpty() && survivors.peek() > 0) { 12 if ((long) survivors.peek() < -(long) current) survivors.pop(); 13 else { 14 if ((long) survivors.peek() == -(long) current) survivors.pop(); 15 alive = false; 16 } 17 } 18 if (alive) survivors.push(current); 19 } 20 int[] answer = new int[survivors.size()]; int write = 0; 21 for (var iterator = survivors.descendingIterator(); iterator.hasNext();) answer[write++] = iterator.next(); 22 return answer; 23 } 24 public static int[] baseline(int[] asteroids) { 25 validate(asteroids); 26 List<Integer> remaining = new ArrayList<>(); for (int value : asteroids) remaining.add(value); 27 while (true) { 28 int i = 0; 29 while (i + 1 < remaining.size() && !(remaining.get(i) > 0 && remaining.get(i + 1) < 0)) i++; 30 if (i + 1 >= remaining.size()) break; 31 long left = remaining.get(i), right = -(long) remaining.get(i + 1); 32 if (left < right) remaining.remove(i); 33 else if (left > right) remaining.remove(i + 1); 34 else { remaining.remove(i + 1); remaining.remove(i); } 35 } 36 return remaining.stream().mapToInt(Integer::intValue).toArray(); 37 } 38 } 39
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Start with the stable result of an empty prefix.
Survivors are displayed in spatial order, with the rightmost at the stack top.
- values
[10,2,-5]- survivorValues
[]
- Introduce the next incoming asteroid.
The incoming is pending; only a positive rightmost survivor can approach a negative incoming.
- values
[10,2,-5]- index
0- incoming
10- alive
true- survivorValues
[]- phase
"incoming"
- Finish this occurrence and restore the stable-prefix invariant.
The settled sequence has no adjacent approaching positive-negative pair. A dead incoming is not appended.
- values
[10,2,-5]- index
0- incoming
10- alive
true- survivorValues
[10]- phase
"settled"
- Introduce the next incoming asteroid.
The incoming is pending; only a positive rightmost survivor can approach a negative incoming.
- values
[10,2,-5]- index
1- incoming
2- alive
true- survivorValues
[10]- phase
"incoming"
- Finish this occurrence and restore the stable-prefix invariant.
The settled sequence has no adjacent approaching positive-negative pair. A dead incoming is not appended.
- values
[10,2,-5]- index
1- incoming
2- alive
true- survivorValues
[10,2]- phase
"settled"
- Introduce the next incoming asteroid.
The incoming is pending; only a positive rightmost survivor can approach a negative incoming.
- values
[10,2,-5]- index
2- incoming
-5- alive
true- survivorValues
[10,2]- phase
"incoming"
- Destroy the smaller top and continue the cascade.
Magnitudes are compared after widening. A surviving incoming may encounter another newly exposed positive top.
- values
[10,2,-5]- index
2- incoming
-5- incomingMagnitude
5- top
2- alive
true- survivorValues
[10]- phase
"collision"
- Destroy the smaller incoming against the larger top.
Magnitudes are compared after widening. A surviving incoming may encounter another newly exposed positive top.
- values
[10,2,-5]- index
2- incoming
-5- incomingMagnitude
5- top
10- alive
false- survivorValues
[10]- phase
"collision"
- Finish this occurrence and restore the stable-prefix invariant.
The settled sequence has no adjacent approaching positive-negative pair. A dead incoming is not appended.
- values
[10,2,-5]- index
2- incoming
-5- alive
false- survivorValues
[10]- phase
"settled"
- Return the contract result.
The completed result follows the declared ordering, empty-state, and numeric semantics.
- result
[10]
Equal sizes annihilate without appending the incoming
Input: [8,-8] · Result: []
Step 1 of 7: Start with the stable result of an empty prefix.
Survivors are displayed in spatial order, with the rightmost at the stack top.
- 0: 8
- 1: -8
Empty at this step.
| Variable | Value |
|---|---|
| values | [8,-8] |
| survivorValues | [] |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[] asteroids) { 4 for (int value : asteroids) if (value == 0) throw new IllegalArgumentException("nonzero asteroids required"); 5 } 6 public static int[] asteroidCollision(int[] asteroids) { 7 validate(asteroids); 8 ArrayDeque<Integer> survivors = new ArrayDeque<>(); 9 for (int current : asteroids) { 10 boolean alive = true; 11 while (alive && current < 0 && !survivors.isEmpty() && survivors.peek() > 0) { 12 if ((long) survivors.peek() < -(long) current) survivors.pop(); 13 else { 14 if ((long) survivors.peek() == -(long) current) survivors.pop(); 15 alive = false; 16 } 17 } 18 if (alive) survivors.push(current); 19 } 20 int[] answer = new int[survivors.size()]; int write = 0; 21 for (var iterator = survivors.descendingIterator(); iterator.hasNext();) answer[write++] = iterator.next(); 22 return answer; 23 } 24 public static int[] baseline(int[] asteroids) { 25 validate(asteroids); 26 List<Integer> remaining = new ArrayList<>(); for (int value : asteroids) remaining.add(value); 27 while (true) { 28 int i = 0; 29 while (i + 1 < remaining.size() && !(remaining.get(i) > 0 && remaining.get(i + 1) < 0)) i++; 30 if (i + 1 >= remaining.size()) break; 31 long left = remaining.get(i), right = -(long) remaining.get(i + 1); 32 if (left < right) remaining.remove(i); 33 else if (left > right) remaining.remove(i + 1); 34 else { remaining.remove(i + 1); remaining.remove(i); } 35 } 36 return remaining.stream().mapToInt(Integer::intValue).toArray(); 37 } 38 } 39
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Start with the stable result of an empty prefix.
Survivors are displayed in spatial order, with the rightmost at the stack top.
- values
[8,-8]- survivorValues
[]
- Introduce the next incoming asteroid.
The incoming is pending; only a positive rightmost survivor can approach a negative incoming.
- values
[8,-8]- index
0- incoming
8- alive
true- survivorValues
[]- phase
"incoming"
- Finish this occurrence and restore the stable-prefix invariant.
The settled sequence has no adjacent approaching positive-negative pair. A dead incoming is not appended.
- values
[8,-8]- index
0- incoming
8- alive
true- survivorValues
[8]- phase
"settled"
- Introduce the next incoming asteroid.
The incoming is pending; only a positive rightmost survivor can approach a negative incoming.
- values
[8,-8]- index
1- incoming
-8- alive
true- survivorValues
[8]- phase
"incoming"
- Equal sizes destroy both.
Magnitudes are compared after widening. A surviving incoming may encounter another newly exposed positive top.
- values
[8,-8]- index
1- incoming
-8- incomingMagnitude
8- top
8- alive
false- survivorValues
[]- phase
"collision"
- Finish this occurrence and restore the stable-prefix invariant.
The settled sequence has no adjacent approaching positive-negative pair. A dead incoming is not appended.
- values
[8,-8]- index
1- incoming
-8- alive
false- survivorValues
[]- phase
"settled"
- Return the contract result.
The completed result follows the declared ordering, empty-state, and numeric semantics.
- result
[]
Test the contract
Input:
[]
Output:[]No asteroids.
Input:
[8,-8]
Output:[]Equal sizes destroy both.
Input:
[5,10,-5]
Output:[5,10]A larger right-moving survivor blocks the incoming.
Input:
[2147483647,-2147483648]
Output:[-2147483648]The minimum int’s magnitude is larger than the maximum positive int.
Common mistakes and counterexamples
Resolve every opposite-sign pair
Counterexample: [-2,1] moves apart, not together.
Collide only positive top with negative incoming.
Stop after one destroyed top
Counterexample: [10,2,-5] needs a second comparison after 2 disappears.
Continue while the incoming is alive and an approaching top remains.
Use Math.abs(int) for all sizes
Counterexample: Math.abs(Integer.MIN_VALUE) is still negative.
Widen before negation and compare long magnitudes.
Follow-ups
Use arbitrary velocities.
Adjacent collisions then depend on relative speeds and times, including same-direction catch-up. The simple sign stack is insufficient; an event-driven simulation needs positions, times, and stale-event handling.
Return survivor identities.
Store original indices with values so equal-sized occurrences remain distinguishable. Emit identities in spatial order and define whether the caller also needs collision history.
Change collision physics.
If objects merge, lose speed, or bounce, a destroyed-top proof may no longer hold. Redefine the state transition and prove stability anew rather than adapting only the magnitude comparison.