aboutsummaryrefslogtreecommitdiff
path: root/range_freq_queries.c
blob: 41f289d7c1b4aa995aac99e80cfb481b49c49efd (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
// 2080. Range Frequency Queries
#include "leetcode.h"

/*
 * design a data structure to find the frequency of a given value in a given
 * subarray. the frequency of a value in a subarray is the number of occurences
 * of that value in the subarray. implement the 'RangeFreqQuery' class:
 * 'rangeFreqQueryCreate(int[] arr)' constructs an instance of the class with
 * the given 0-indexed integer array 'arr'. 'int RangeFreqQuery(int left, int
 * right, int val)' returns the frequency of 'val' in the subarray 'arr[left ...
 * right]'. a subarray is contiguous sequence of elements within an array.
 * 'arr[left ... right]' denotes the subarray that contains the elements of
 * 'nums' between indices 'left' and 'right' inclusively
 */

typedef struct {
  int *a;
  int size;
} RangeFreqQuery;

int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }

RangeFreqQuery *rangeFreqQueryCreate(int *arr, int arrSize) {
  RangeFreqQuery *obj = (RangeFreqQuery *)calloc(1, sizeof(RangeFreqQuery));
  obj->size = arrSize + 1;
  obj->a = (int *)calloc(obj->size, sizeof(int));
  for (int i = 0; i < arrSize; i++)
    obj->a[i] = arr[i] << 17 | i;
  obj->a[arrSize] = 10001 << 17;
  qsort(obj->a, obj->size - 1, sizeof(int), cmp);
  return obj;
}

int bsearch1(int *a, int size, int target) {
  int l = 0, r = size - 1, m;
  while (l < r) {
    m = l + ((r - l) >> 1);
    if (a[m] < target)
      l = m + 1;
    else
      r = m;
  }
  return l;
}

int bsearch2(int *a, int size, int target) {
  int l = 0, r = size - 1, m;
  while (l < r) {
    m = l + ((r - l) >> 1);
    if (a[m] <= target)
      l = m + 1;
    else
      r = m;
  }
  return l;
}

int rangeFreqQueryQuery(RangeFreqQuery *obj, int left, int right, int value) {
  int l = bsearch1(obj->a, obj->size, value << 17 | left);
  int r = bsearch2(obj->a, obj->size, value << 17 | right);
  return r - l;
}

void rangeFreqQueryFree(RangeFreqQuery *obj) {
  free(obj->a);
  free(obj);
}

int main() {
  int arr[] = {12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56};
  RangeFreqQuery *obj = rangeFreqQueryCreate(arr, ARRAY_SIZE(arr));
  printf("%d\n", rangeFreqQueryQuery(obj, 1, 2, 4));   // expect: 1
  printf("%d\n", rangeFreqQueryQuery(obj, 0, 11, 33)); // expect: 2
  rangeFreqQueryFree(obj);
}