diff options
-rw-r--r-- | find_distinct_ball_colour.c | 149 | ||||
-rw-r--r-- | find_distinct_ball_colour.py | 38 |
2 files changed, 187 insertions, 0 deletions
diff --git a/find_distinct_ball_colour.c b/find_distinct_ball_colour.c new file mode 100644 index 0000000..6c08491 --- /dev/null +++ b/find_distinct_ball_colour.c @@ -0,0 +1,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); +} diff --git a/find_distinct_ball_colour.py b/find_distinct_ball_colour.py new file mode 100644 index 0000000..4c7da6a --- /dev/null +++ b/find_distinct_ball_colour.py @@ -0,0 +1,38 @@ +# 3160. Find the Number of Distinct colours Among the Balls + +""" +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. +""" + + +class Solution(object): + def queryResults(self, limit, queries): + """ + :type limit: int + :type queries: List[List[int]] + :rtype: List[int] + """ + colours, cnt, ans = {}, {}, [] + for i in queries: + ball, colour = i + if ball in colours: + prev = colours[ball] + cnt[prev] -= 1 + if cnt[prev] == 0: + del cnt[prev] + colours[ball] = colour + cnt[colour] = cnt.get(colour, 0) + 1 + ans.append(len(cnt)) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.queryResults(limit=4, queries=[[1, 4], [2, 5], [1, 3], [3, 4]])) + print(obj.queryResults(limit=4, queries=[[0, 1], [1, 2], [2, 2], [3, 4], [4, 5]])) |