-
Notifications
You must be signed in to change notification settings - Fork 889
/
AsteroidCollision.swift
42 lines (36 loc) · 1.24 KB
/
AsteroidCollision.swift
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
/**
* Question Link: https://leetcode.com/problems/asteroid-collision/
* Primary idea: traverse the array and handle positive and negative separately
*
* Time Complexity: O(n), Space Complexity: O(n)
*
*/
class AsteroidCollision {
func asteroidCollision(_ asteroids: [Int]) -> [Int] {
var positives = [Int]()
var negatives = [Int]()
for asteroid in asteroids {
if asteroid > 0 {
positives.append(asteroid)
} else {
var shouldAppendToNegative = true
while positives.count > 0 {
if positives.last! > -asteroid {
shouldAppendToNegative = false
break
} else {
let last = positives.removeLast()
if -asteroid == last {
shouldAppendToNegative = false
break
}
}
}
if shouldAppendToNegative {
negatives.append(asteroid)
}
}
}
return negatives + positives
}
}