aboutsummaryrefslogtreecommitdiff
path: root/find_distinct_ball_colour.c
blob: 6c0849146654d0ce97cdcc9bf2a5db304e9a57e7 (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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
// 3160. Find the Number of Distinct Colors Among the Balls
#include "leetcode.h"

/*
 * you are given an integer 'limit' and a 2d array 'queries' of size 'n x 2'.
 * there are 'limit + 1' balls with distinct labels in the range '[0, limit]'.
 * initially, all balls are uncoloured. for every query in 'queries' that is of
 * the form '[x, y]', you makr ball 'x' with the colour 'y'. after each query,
 * you need to find the number of distinct colours among the balls. return an
 * array 'result' of length 'n' where 'result[i]' denotes the number of distinct
 * colours after the i'th query.
 */

#define MOD 1009

struct item {
  int colour;
  int freq;
  struct item *next;
};

struct ball {
  int id;
  int colour;
  struct ball *next;
};

struct item *hash[MOD];
struct ball *ball[MOD];

void ball_init(void) { memset((void *)ball, 0, sizeof(ball)); }

void ball_set(int id, int colour) {
  int key = id % MOD;
  for (struct ball *header = ball[key]; header; header = header->next)
    if (header->id == id) {
      header->colour = colour;
      return;
    }
  struct ball *new = (struct ball *)malloc(sizeof(struct ball));
  new->id = id;
  new->colour = colour;
  new->next = ball[key];
  ball[key] = new;
}

int ball_get(int id, int *colour) {
  int key = id % MOD;
  for (struct ball *header = ball[key]; header; header = header->next)
    if (header->id == id) {
      *colour = header->colour;
      return 0;
    }
  return -1;
}

void ball_free(void) {
  for (int i = 0; i < MOD; i++)
    for (struct ball *header = ball[i], *del; header;) {
      del = header;
      header = header->next;
      free(del);
    }
}

void hash_init() { memset((void *)hash, 0, sizeof(hash)); }

int hash_get(int colour, int *freq) {
  int key = colour % MOD;
  for (struct item *header = hash[key]; header; header = header->next)
    if (header->colour == colour) {
      *freq = header->freq;
      return 0;
    }
  return -1;
}

void hash_set(int colour, int freq) {
  int key = colour % MOD;
  for (struct item *header = hash[key]; header; header = header->next)
    if (header->colour == colour) {
      header->freq = freq;
      return;
    }
  struct item *new = (struct item *)malloc(sizeof(struct item));
  new->colour = colour;
  new->freq = freq;
  new->next = hash[key];
  hash[key] = new;
}

void hash_free(void) {
  for (int i = 0; i < MOD; i++)
    for (struct item *header = hash[i], *del; header;) {
      del = header;
      header = header->next;
      free(del);
    }
}

int *queryResults(int limit, int **queries, int queriesSize,
                  int *queriesColSize, int *returnSize) {
  int distinct = 0, *ans = (int *)malloc(queriesSize * sizeof(int));
  hash_init();
  ball_init();
  for (int i = 0; i < queriesSize; i++) {
    int freq, ball_colour = 0;
    ball_get(queries[i][0], &ball_colour);
    if (ball_colour) {
      hash_get(ball_colour, &freq);
      freq--;
      hash_set(ball_colour, freq);
      if (!freq)
        distinct--;
    }
    ball_set(queries[i][0], queries[i][1]);
    freq = 0;
    hash_get(queries[i][1], &freq);
    freq++;
    if (freq == 1)
      distinct++;
    hash_set(queries[i][1], freq);
    ans[i] = distinct;
  }
  hash_free();
  ball_free();
  *returnSize = queriesSize;
  return ans;
}

int main() {
  int q1i[4][2] = {{1, 4}, {2, 5}, {1, 3}, {3, 4}}, rs1;
  int q2i[5][2] = {{0, 1}, {1, 2}, {2, 2}, {3, 4}, {4, 5}}, rs2;
  struct two_d_arr q1, q2;
  two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
  two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i);
  int *qr1 = queryResults(4, q1.arr, q1.row_size, q1.col_size, &rs1);
  int *qr2 = queryResults(4, q2.arr, q2.row_size, q2.col_size, &rs2);
  for (int i = 0; i < rs1; i++)
    printf("%d ", qr1[i]); // expect: 1 2 2 3
  printf("\n");
  for (int i = 0; i < rs2; i++)
    printf("%d ", qr2[i]); // expect: 1 2 2 3 4
  printf("\n");
  free(qr1);
  free(qr2);
  two_d_arr_free(&q1);
  two_d_arr_free(&q2);
}