aboutsummaryrefslogtreecommitdiff
path: root/len_longest_subarr_k.c
diff options
context:
space:
mode:
Diffstat (limited to 'len_longest_subarr_k.c')
-rw-r--r--len_longest_subarr_k.c50
1 files changed, 50 insertions, 0 deletions
diff --git a/len_longest_subarr_k.c b/len_longest_subarr_k.c
new file mode 100644
index 0000000..706483c
--- /dev/null
+++ b/len_longest_subarr_k.c
@@ -0,0 +1,50 @@
+// 2958. Length of Longest Subarray With at Most K Frequency
+#include "leetcode.h"
+
+/*
+ * given an integer array 'nums' and an integer 'k'. the frequency of an element
+ * x is the number of times it occurs in an array. an array is called good if
+ * the frequency of each element in this array is less than or equal to 'k'.
+ * return the length of the longest good subarray of 'nums' a subarray is a
+ * contiguous non empty sequence of elements within an array
+ */
+
+typedef struct {
+ UT_hash_handle hh;
+ int num;
+ int cnt;
+} h_elem;
+
+int maxSubarrayLength(int *nums, int numsSize, int k) {
+ h_elem *freq = NULL, *t, *s;
+ int left = 0, more = 0;
+ for (int right = 0; right < numsSize; right++) {
+ HASH_FIND_INT(freq, &nums[right], t);
+ if (t) {
+ t->cnt++;
+ } else {
+ t = calloc(sizeof(h_elem), 1);
+ t->num = nums[right];
+ t->cnt = 1;
+ HASH_ADD_INT(freq, num, t);
+ }
+ if (t->cnt == k + 1)
+ more++;
+ if (more) {
+ HASH_FIND_INT(freq, &nums[left], s);
+ s->cnt--;
+ if (s->cnt == k)
+ more--;
+ left++;
+ }
+ }
+ return numsSize - left;
+}
+
+int main() {
+ int n1[] = {1, 2, 3, 1, 2, 3, 1, 2}, n2[] = {1, 2, 1, 2, 1, 2, 1, 2},
+ n3[] = {5, 5, 5, 5, 5, 5, 5};
+ printf("%d\n", maxSubarrayLength(n1, ARRAY_SIZE(n1), 2)); // expect: 6
+ printf("%d\n", maxSubarrayLength(n2, ARRAY_SIZE(n2), 1)); // expect: 2
+ printf("%d\n", maxSubarrayLength(n3, ARRAY_SIZE(n3), 4)); // expect: 4
+}