aboutsummaryrefslogtreecommitdiff
path: root/range_freq_queries.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-20 17:38:34 -0600
committerJack Sangdahl <[email protected]>2024-08-20 17:38:34 -0600
commit53ef9811af1c9e013ba8e9f379ea67724ffc0281 (patch)
tree784ea191a74eb03a43346897c0efb2f5f0ad0b41 /range_freq_queries.c
parentb756e65c613e0f145c671d089e30b62ae6f63959 (diff)
downloadleetcode-53ef9811af1c9e013ba8e9f379ea67724ffc0281.tar.gz
leetcode-53ef9811af1c9e013ba8e9f379ea67724ffc0281.zip
2080. range frequency queries
Diffstat (limited to 'range_freq_queries.c')
-rw-r--r--range_freq_queries.c75
1 files changed, 75 insertions, 0 deletions
diff --git a/range_freq_queries.c b/range_freq_queries.c
new file mode 100644
index 0000000..41f289d
--- /dev/null
+++ b/range_freq_queries.c
@@ -0,0 +1,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);
+}