aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-05 21:41:11 -0600
committerJack Sangdahl <[email protected]>2024-10-05 21:41:11 -0600
commit071f544d646729018aeba458dd7fa8e20f71d58a (patch)
tree6b97ae6092643a7206b9b8fc2639d3d56952ef3a
parentb4d0b099e1641df61f69df63c2204d42c11c1ba7 (diff)
downloadleetcode-071f544d646729018aeba458dd7fa8e20f71d58a.tar.gz
leetcode-071f544d646729018aeba458dd7fa8e20f71d58a.zip
2200. find all k-distant indices in an array
-rw-r--r--find_k_distant_indices.c39
-rw-r--r--find_k_distant_indices.py34
2 files changed, 73 insertions, 0 deletions
diff --git a/find_k_distant_indices.c b/find_k_distant_indices.c
new file mode 100644
index 0000000..df236c5
--- /dev/null
+++ b/find_k_distant_indices.c
@@ -0,0 +1,39 @@
+// 2200. Find All K-Distant Indices in an Array
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed integer array 'nums' and two integers 'key' and 'k'
+ * a k-distant index is an index 'i' of 'nums' for which there exists at least
+ * one index 'j' such that '|i - j| <= k' and 'nums[j] == key'. return a list of
+ * all k-distant indices sorted in increasing order
+ */
+
+int *findKDistantIndices(int *nums, int numsSize, int key, int k,
+ int *returnSize) {
+ int *ans = (int *)calloc(numsSize, sizeof(int));
+ int ans_idx = 0, i = 0;
+ while (i < numsSize) {
+ if (nums[i] == key) {
+ int prev_idx = !ans_idx ? -1 : ans[ans_idx - 1];
+ int start_idx = i - k > prev_idx ? i - k : prev_idx + 1;
+ for (int j = start_idx; j <= i + k && j < numsSize; j++)
+ ans[ans_idx++] = j;
+ }
+ i++;
+ }
+ *returnSize = ans_idx;
+ return ans;
+}
+
+int main() {
+ int n1[] = {3, 4, 9, 1, 3, 9, 5}, n2[] = {2, 2, 2, 2, 2}, rs1, rs2;
+ int *fkdi1 = findKDistantIndices(n1, ARRAY_SIZE(n1), 9, 1, &rs1);
+ int *fkdi2 = findKDistantIndices(n2, ARRAY_SIZE(n2), 2, 2, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", fkdi1[i]); // expect: 1 2 3 4 5 6
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", fkdi2[i]); // expect: 0 1 2 3 4
+ printf("\n");
+ free(fkdi1), free(fkdi2);
+}
diff --git a/find_k_distant_indices.py b/find_k_distant_indices.py
new file mode 100644
index 0000000..11ddfc6
--- /dev/null
+++ b/find_k_distant_indices.py
@@ -0,0 +1,34 @@
+# 2200. Find All K-Distant Indices in an Array
+import bisect
+
+"""
+you are given a 0-indexed integer array 'nums' and two integers 'key' and 'k'
+a k-distant index is an index 'i' of 'nums' for which there exists at least
+one index 'j' such that '|i - j| <= k' and 'nums[j] == key'. return a list of
+all k-distant indices sorted in increasing order
+"""
+
+
+class Solution(object):
+ def findKDistantIndices(self, nums, key, k):
+ """
+ :type nums: List[int]
+ :type key: int
+ :type k: int
+ :rtype: List[int]
+ """
+ keys = [i for (i, j) in enumerate(nums) if j == key]
+ ans = set(keys)
+ for i in range(len(nums)):
+ idx = bisect.bisect_left(keys, i)
+ if 0 <= idx < len(keys) and abs(i - keys[idx]) <= k:
+ ans.add(i)
+ if 0 < idx <= len(keys) and abs(i - keys[idx - 1]) <= k:
+ ans.add(i)
+ return sorted(list(ans))
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findKDistantIndices(nums=[3, 4, 9, 1, 3, 9, 5], key=9, k=1))
+ print(obj.findKDistantIndices(nums=[2, 2, 2, 2, 2], key=2, k=2))