aboutsummaryrefslogtreecommitdiff
path: root/asteroid_collision.c
blob: 3d7393a14ee2b5f066977143e37bf18ef8d2a6ee (plain)
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
// 735. Asteroid Collision
#include <stdio.h>
#include <stdlib.h>

/*
 * given an array 'asteroids' o intergers representing asteroids in a row. for
 * each asteroid, the absolute value represents its size, and the sign
 * represents its direction (positive meaning right, negative meaning left).
 * each asteroid moves at the same speed. find out the state of the asteroids
 * after all collisions. if two asteroids meet the smaller one will explode. if
 * both are the same size, both will explode. two asteroids moving in the same
 * direction will never meet.
 */

int *asteroidCollision(int *asteroids, int asteroids_size, int *return_size) {
  int n = asteroids_size, ans_idx = 0;
  int *ans = malloc(n * sizeof(int));
  ans[ans_idx] = asteroids[ans_idx];
  for (int i = 0; i < n; i++) {
    ans_idx++;
    ans[ans_idx] = asteroids[i];
    while (ans_idx && ans[ans_idx] < 0 && ans[ans_idx - 1]) {
      if (abs(ans[ans_idx]) == abs(ans[ans_idx - 1])) {
        ans_idx -= 2;
        continue;
      }
      if (abs(ans[ans_idx]) > abs(ans[ans_idx - 1])) {
        ans[ans_idx - 1] = ans[ans_idx];
        ans_idx--;
      } else
        ans_idx--;
    }
  }
  *return_size = ans_idx + 1;
  ans = realloc(ans, (*return_size) * sizeof(int));
  return ans;
}

int main() {
  int a1[] = {5, 10, -5}, a2[] = {8, -8}, a3[] = {10, 2, -5};
  int as1 = 3, as2 = 2, as3 = 3;
  int rs1[] = {}, rs2[] = {}, rs3[] = {};
  int *ac1 = asteroidCollision(a1, as1, rs1);
  int *ac2 = asteroidCollision(a2, as2, rs2);
  int *ac3 = asteroidCollision(a3, as3, rs3);
  for (int i = 0; i < as1; i++)
    printf("%d ", ac1[i]); // expect: 5 10
  printf("\n");
  for (int i = 0; i < as2; i++)
    printf("%d ", ac2[i]); // expect:
  printf("\n");
  for (int i = 0; i < as3; i++)
    printf("%d ", ac3[i]); // expect: 10
  printf("\n");
}