leetcode

commit 1f00ecabf08fcb91339dde49c06c5295703b66c2
parent d1fb87cbb1e1978a63165c5b3685c866e86e9373
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri, 17 Oct 2025 21:27:15 -0600

3397. maximum number of distinct elements after operations

Diffstat:
A
max_num_distinct_elemt_op.c
 | 
31
+++++++++++++++++++++++++++++++
A
max_num_distinct_elemt_op.py
 | 
28
++++++++++++++++++++++++++++

2 files changed, 59 insertions(+), 0 deletions(-)
diff --git a/max_num_distinct_elemt_op.c b/max_num_distinct_elemt_op.c
@@ -0,0 +1,31 @@
+// 3397. Maximum Number of Distinct Elements After Operations
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' and an integer 'k'. you are allowed to
+ * perform the following operation on each element of the array at most once:
+ * add a single integer in the range '[-k, k]' to the element. return the
+ * maximum possible number of distinct elements in 'nums' after performing the
+ * operation.
+ */
+
+int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
+
+int maxDistinctElements(int *nums, int numsSize, int k) {
+  qsort(nums, numsSize, sizeof(int), cmp);
+  int ans = 0, prev = INT_MIN;
+  for (int i = 0; i < numsSize; i++) {
+    int j = fmax(nums[i] - k, prev + 1);
+    if (j <= nums[i] + k) {
+      prev = j;
+      ans++;
+    }
+  }
+  return ans;
+}
+
+int main() {
+  int n1[] = {1, 2, 2, 3, 3, 4}, n2[] = {4, 4, 4, 4};
+  printf("%d\n", maxDistinctElements(n1, ARRAY_SIZE(n1), 2)); // expect: 6
+  printf("%d\n", maxDistinctElements(n2, ARRAY_SIZE(n2), 1)); // expect: 3
+}
diff --git a/max_num_distinct_elemt_op.py b/max_num_distinct_elemt_op.py
@@ -0,0 +1,28 @@
+# 611. Valid Triangle Number
+
+"""
+given an integer array 'nums', return the number of triplets chosen from the
+array that can make triangles if we take them as side lengths of a triangle
+"""
+
+
+class Solution(object):
+    def maxDistinctElements(self, nums, k):
+        """
+        :type nums: List[int]
+        :type k: int
+        :rtype: int
+        """
+        nums.sort()
+        ans, prev = 0, float("-inf")
+        for i in nums:
+            if max(i - k, prev + 1) <= i + k:
+                prev = max(i - k, prev + 1)
+                ans += 1
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.maxDistinctElements(nums=[1, 2, 2, 3, 3, 4], k=2))
+    print(obj.maxDistinctElements(nums=[4, 4, 4, 4], k=1))