aboutsummaryrefslogtreecommitdiff
path: root/avoid_flood_city.c
blob: 86f304d988dc9dc8bbf3bc0e989c9a6c6c9f2d0c (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
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
// 1488. Avoid Flood in The City
#include "leetcode.h"

/*
 * your country has an infinite number of lakes. initially, all the lakes are
 * empty. but when it rains over the n'th lake, the n'th lake becomes full of
 * water. if it rains over a lake that is full of water, there will be a flood.
 * your goal is to avoid any floods. if there are multiple valid answers, return
 * any of them. if it is impossible to avoid flood, return an empty array.
 * notice that if yo uchose to dry a full lake, it becomes empty. but if you
 * chose to dry an empty lake, nothing happens.
 */

int *avoidFlood(int *rains, int rainsSize, int *returnSize) {
  *returnSize = rainsSize;
  int s_idx = 0, top = 0, n = 2 * rainsSize;
  int *ans = (int *)calloc(rainsSize, sizeof(int));
  int *stack = (int *)malloc(rainsSize * sizeof(int));
  int **hash = (int **)calloc(n, sizeof(int *));
  for (int i = 0; i < rainsSize; i++) {
    if (!rains[i]) {
      stack[s_idx] = i;
      s_idx++;
      ans[i] = 1;
    } else {
      ans[i] = -1;
      int val = rains[i], d = val;
      while (1) {
        if (!hash[d % n]) {
          hash[d % n] = (int *)malloc(2 * sizeof(int));
          hash[d % n][0] = val;
          hash[d % n][1] = i;
          break;
        } else if (hash[d % n][0] == val) {
          if (top == s_idx) {
            *returnSize = 0;
            goto exit;
          }
          for (int j = top; j < s_idx; i++) {
            if (stack[j] > hash[d % n][1]) {
              ans[stack[j]] = val;
              stack[j] = -1;
              hash[d % n][1] = i;
              break;
            }
            if (j == s_idx - 1) {
              *returnSize = 0;
              goto exit;
            }
          }
          break;
        } else
          d++;
      }
      while (top < s_idx && stack[top] == -1)
        top++;
    }
  }
exit:
  free(stack);
  for (int i = 0; i < n; i++)
    if (hash[i])
      free(hash[i]);
  free(hash);
  return ans;
}

int main() {
  int r1[] = {1, 2, 3, 4}, r2[] = {1, 2, 0, 0, 2, 1}, r3[] = {1, 2, 0, 1, 2};
  int rs1, *af1 = avoidFlood(r1, ARRAY_SIZE(r1), &rs1);
  int rs2, *af2 = avoidFlood(r2, ARRAY_SIZE(r2), &rs2);
  int rs3, *af3 = avoidFlood(r3, ARRAY_SIZE(r3), &rs3);
  for (int i = 0; i < rs1; i++)
    printf("%d ", af1[i]); // expect: -1 -1 -1 -1
  printf("\n");
  for (int i = 0; i < rs2; i++)
    printf("%d ", af2[i]); // expect:  -1 -1 2 1 -1 -1
  printf("\n");
  for (int i = 0; i < rs3; i++)
    printf("%d ", af3[i]); // expect: null
  printf("\n");
  free(af1);
  free(af2);
  free(af3);
}