aboutsummaryrefslogtreecommitdiff
path: root/intervals_between_identical_element.c
blob: 3a3b4d6018d8308680f59a4c5120f0a018360a15 (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
// 2121. Intervals Between Identical Elements
#include "leetcode.h"

/*
 * given a 0-indexed array of 'n' integers 'arr'. the interval between two
 * elements in 'arr' is defined as the absolute difference between their
 * indices. more formally, the interval between 'arr[i]' and 'arr[j]' is |i -
 * j|. return an array intervals of length 'n' where 'intervals[i]' is the sum
 * of the intervals between 'arr[i]' and each element in 'arr' with the same
 * value as 'arr[i]'.
 */

typedef struct {
  int value;
  uint64_t idx_sum;
  int idx_max;
  int idx_cnt;
  int *idx;
} node;

typedef struct {
  int size;
  node *n;
} hash;

node *hash_find(hash *h, int v) {
  int idx = v % h->size;
  for (int i = 0; i < h->size; i++) {
    int curr_idx = (idx + i) % h->size;
    node *curr = &h->n[curr_idx];
    if (!curr->idx_cnt || curr->value == v)
      return curr;
  }
  return NULL;
}

long long *getDistances(int *arr, int arrSize, int *returnSize) {
  long long *ans = calloc(arrSize, sizeof(long long));
  hash h = {0, NULL};
  h.size = arrSize * 2;
  h.n = calloc(h.size, sizeof(node));
  for (int i = 0; i < arrSize; i++) {
    node *curr = hash_find(&h, arr[i]);
    if (!curr->idx_cnt) {
      curr->value = arr[i];
      curr->idx_max = 10;
      curr->idx = calloc(curr->idx_max, sizeof(int));
    }
    if (curr->idx_cnt == curr->idx_max) {
      curr->idx_max *= 2;
      curr->idx = realloc(curr->idx, curr->idx_max * sizeof(int));
    }
    curr->idx[curr->idx_cnt++] = i;
    curr->idx_sum += i;
  }
  for (int i = 0; i < h.size; i++) {
    node *curr = &h.n[i];
    if (curr->idx_cnt) {
      uint64_t pre_sum = 0, post_sum = curr->idx_sum;
      for (int j = 0; j < curr->idx_cnt; j++) {
        uint64_t curr_idx = curr->idx[j];
        post_sum -= curr_idx;
        ans[curr_idx] = (j * curr_idx - pre_sum) +
                        (post_sum - (curr->idx_cnt - j - 1) * curr_idx);
        pre_sum += curr_idx;
      }
      free(curr->idx);
    }
  }
  free(h.n);
  *returnSize = arrSize;
  return ans;
}

int main() {
  int a1[] = {2, 1, 3, 1, 2, 3, 3}, a2[] = {10, 5, 10, 10};
  int rs1 = 0, rs2 = 0;
  long long *gd1 = getDistances(a1, ARRAY_SIZE(a1), &rs1);
  long long *gd2 = getDistances(a2, ARRAY_SIZE(a2), &rs2);
  for (int i = 0; i < ARRAY_SIZE(a1); i++)
    printf("%lld ", gd1[i]); // expect: [4,2,7,2,4,4,5]
  printf("\n");
  for (int i = 0; i < ARRAY_SIZE(a2); i++)
    printf("%lld ", gd2[i]); // expect: [5,0,3,4]
  printf("\n");
  free(gd1), free(gd2);
}