commit ec44665d6c0a4bcd1402ece43e6885f6edd1cfba
parent 76a1d75d72373fe3dbdc5176b44f39fc7c32e341
Author: Jack Sangdahl <jack@pngu.org>
Date: Tue, 21 Oct 2025 18:38:03 -0600
3347. maximum frequency of an element after performing operations 2
Diffstat:
2 files changed, 195 insertions(+), 0 deletions(-)
diff --git a/max_freq_elem_op2.c b/max_freq_elem_op2.c
@@ -0,0 +1,137 @@
+// 3347. Maximum Frequency of an Element After Performing Operations II
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' and two integers 'k' and
+ * 'numOperations'. you must perform an operation 'numOperations' times on
+ * 'nums', where in each operation you select an index 'i' that was not selected
+ * in any previous operations, and add an integer in the range '[-k, k]' to
+ * 'nums[i]'. return the maximum possible frequency of any elements in 'nums'
+ * after performing the operations.
+ */
+
+struct hash_item {
+ int key;
+ int val;
+ UT_hash_handle hh;
+};
+
+struct hash_item *hash_find_item(struct hash_item **obj, int key) {
+ struct hash_item *p = NULL;
+ HASH_FIND_INT(*obj, &key, p);
+ return p;
+}
+
+bool hash_add_item(struct hash_item **obj, int key, int val) {
+ if (hash_find_item(obj, key))
+ return false;
+ struct hash_item *p = (struct hash_item *)malloc(sizeof(struct hash_item));
+ p->key = key;
+ p->val = val;
+ HASH_ADD_INT(*obj, key, p);
+ return true;
+}
+
+void hash_set_item(struct hash_item **obj, int key, int val) {
+ struct hash_item *p = hash_find_item(obj, key);
+ if (!p)
+ hash_add_item(obj, key, val);
+ else
+ p->val = val;
+}
+
+int hash_get_item(struct hash_item **obj, int key, int val) {
+ struct hash_item *p = hash_find_item(obj, key);
+ if (!p)
+ return val;
+ return p->val;
+}
+
+void hash_free(struct hash_item **obj) {
+ struct hash_item *curr = NULL, *tmp = NULL;
+ HASH_ITER(hh, *obj, curr, tmp) {
+ HASH_DEL(*obj, curr);
+ free(curr);
+ }
+}
+
+int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
+
+void add_mode(int *nums, int numsSize, int k, struct hash_item **modes,
+ int val) {
+ hash_add_item(modes, val, 1);
+ if (val - k >= nums[0])
+ hash_add_item(modes, val - k, 1);
+ if (val + k <= nums[numsSize - 1])
+ hash_add_item(modes, val + k, 1);
+}
+
+int left_bound(int *nums, int numsSize, int val) {
+ int left = 0, right = numsSize - 1;
+ while (left < right) {
+ int mid = (left + right) / 2;
+ if (nums[mid] < val)
+ left = mid + 1;
+ else
+ right = mid;
+ }
+ return left;
+}
+
+int right_bound(int *nums, int numsSize, int val) {
+ int left = 0, right = numsSize - 1;
+ while (left < right) {
+ int mid = (left + right + 1) / 2;
+ if (nums[mid] > val)
+ right = mid - 1;
+ else
+ left = mid;
+ }
+ return left;
+}
+
+int maxFrequency(int *nums, int numsSize, int k, int numOperations) {
+ qsort(nums, numsSize, sizeof(int), cmp);
+ int ans = 0, prev = 0;
+ struct hash_item *num_cnt = NULL, *modes = NULL;
+ for (int i = 0; i < numsSize; i++) {
+ if (nums[i] != nums[prev]) {
+ hash_set_item(&num_cnt, nums[prev], i - prev);
+ if (i - prev > ans)
+ ans = i - prev;
+ add_mode(nums, numsSize, k, &modes, nums[prev]);
+ prev = i;
+ }
+ }
+ hash_set_item(&num_cnt, nums[prev], numsSize - prev);
+ if (numsSize - prev > ans)
+ ans = numsSize - prev;
+ add_mode(nums, numsSize, k, &modes, nums[prev]);
+ int mode_size = HASH_COUNT(modes), pos = 0;
+ int *sorted_modes = (int *)malloc(mode_size * sizeof(int));
+ for (struct hash_item *p = modes; p; p = p->hh.next)
+ sorted_modes[pos++] = p->key;
+ qsort(sorted_modes, mode_size, sizeof(int), cmp);
+ for (int i = 0; i < mode_size; i++) {
+ int mode = sorted_modes[i], tmp;
+ int l = left_bound(nums, numsSize, mode - k);
+ int r = right_bound(nums, numsSize, mode + k);
+ if (hash_find_item(&num_cnt, mode)) {
+ int cnt = hash_get_item(&num_cnt, mode, 0);
+ tmp = fmin(r - l + 1, cnt + numOperations);
+ } else
+ tmp = fmin(r - l + 1, numOperations);
+ if (tmp > ans)
+ ans = tmp;
+ }
+ hash_free(&num_cnt);
+ hash_free(&modes);
+ free(sorted_modes);
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 4, 5}, n2[] = {5, 11, 20, 20};
+ printf("%d\n", maxFrequency(n1, ARRAY_SIZE(n1), 1, 2)); // expect: 2
+ printf("%d\n", maxFrequency(n2, ARRAY_SIZE(n2), 5, 1)); // expect: 2
+}
diff --git a/max_freq_elem_op2.py b/max_freq_elem_op2.py
@@ -0,0 +1,58 @@
+# 3347. Maximum Frequency of an Element After Performing Operations II
+import bisect
+from collections import defaultdict
+
+"""
+you are given an integer array 'nums' and two integers 'k' and
+'numOperations'. you must perform an operation 'numOperations' times on
+'nums', where in each operation you select an index 'i' that was not selected
+in any previous operations, and add an integer in the range '[-k, k]' to
+'nums[i]'. return the maximum possible frequency of any elements in 'nums'
+after performing the operations.
+"""
+
+
+class Solution(object):
+ def maxFrequency(self, nums, k, numOperations):
+ """
+ :type nums: List[int]
+ :type k: int
+ :type numOperations: int
+ :rtype: int
+ """
+ nums.sort()
+ ans, modes = 0, set()
+ num_cnt = defaultdict(int)
+
+ def add_mode(value):
+ modes.add(value)
+ if value - k >= nums[0]:
+ modes.add(value - k)
+ if value + k <= nums[-1]:
+ modes.add(value + k)
+
+ prev = 0
+ for i in range(len(nums)):
+ if nums[i] != nums[prev]:
+ num_cnt[nums[prev]] = i - prev
+ ans = max(ans, i - prev)
+ add_mode(nums[prev])
+ prev = i
+ num_cnt[nums[prev]] = len(nums) - prev
+ ans = max(ans, len(nums) - prev)
+ add_mode(nums[prev])
+ for mode in sorted(modes):
+ l = bisect.bisect_left(nums, mode - k)
+ r = bisect.bisect_right(nums, mode + k) - 1
+ if mode in num_cnt:
+ tmp = min(r - l + 1, num_cnt[mode] + numOperations)
+ else:
+ tmp = min(r - l + 1, numOperations)
+ ans = max(ans, tmp)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxFrequency(nums=[1, 4, 5], k=1, numOperations=2))
+ print(obj.maxFrequency(nums=[5, 11, 20, 20], k=5, numOperations=1))
