-
Notifications
You must be signed in to change notification settings - Fork 0
/
AsteroidCollison.java
96 lines (83 loc) · 2.94 KB
/
AsteroidCollison.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package stack;
import java.util.*;
//https://leetcode.com/problems/asteroid-collision/
//735. Asteroid Collision
public class AsteroidCollison {
public static void main(String[] args) {
AsteroidCollison a= new AsteroidCollison();
int as[]= {-2,-1,1,2};
a.asteroidCollision(as);
}
/**
*
* @param asteroids
* @return
*/
public int[] asteroidCollision(int[] asteroids) {
if(asteroids.length==0) return asteroids;
Stack<Integer> st= new Stack<>();
for(int i=0;i<asteroids.length;i++){
if(asteroids[i]>0){
st.push(asteroids[i]);
}else{
int curr=asteroids[i];
while(!st.isEmpty() &&
st.peek() < Math.abs(asteroids[i]) // last asteroids is smaller
&& st.peek() > 0 )// last value is positive
{
st.pop();
}
if(st.isEmpty() //Its already empty add current
|| st.peek()<0)// both current and last are -ve so cant collide
{
st.add(asteroids[i] );
}
else if(st.peek()==Math.abs(asteroids[i])
){
st.pop();
}
}
}
int res[]=new int[st.size()];
int i=st.size()-1;
while(!st.isEmpty()){
res[i]=st.pop();
i--;
}
return res;
}
/**
* Below solution is without stack and using a list
* @param asteroids
* @return
*/
public int[] asteroidCollisionWithoutStack(int[] asteroids) {
if(asteroids.length==0) return asteroids;
List<Integer> results= new ArrayList<>();
for(int i=0; i<asteroids.length;i++){
results.add(asteroids[i]);
if(i>0 && results.size()>1){
int last=results.get(results.size()-2);
int current= results.get(results.size()-1);
while(last>0 && current<0){
if(Math.abs(last) > Math.abs(current) ){
results.remove(results.size()-1);
} else if(Math.abs(last) < Math.abs(current) ){
results.remove(results.size()-2);
} else {
results.remove(results.size()-1);
results.remove(results.size()-1);
}
if(results.size()>1) {
last=results.get(results.size()-2);
current= results.get(results.size()-1);
}else{
break;
}
}
}
}
//System.out.println(results);
return results.stream().mapToInt(i->i).toArray();
}
}