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.
Example 1:
Input: nums = [3,4,9,1,3,9,5], key = 9, k = 1 Output: [1,2,3,4,5,6] Explanation: Here,nums[2] == keyandnums[5] == key. - For index 0, |0 - 2| > k and |0 - 5| > k, so there is no jwhere|0 - j| <= kandnums[j] == key. Thus, 0 is not a k-distant index. - For index 1, |1 - 2| <= k and nums[2] == key, so 1 is a k-distant index. - For index 2, |2 - 2| <= k and nums[2] == key, so 2 is a k-distant index. - For index 3, |3 - 2| <= k and nums[2] == key, so 3 is a k-distant index. - For index 4, |4 - 5| <= k and nums[5] == key, so 4 is a k-distant index. - For index 5, |5 - 5| <= k and nums[5] == key, so 5 is a k-distant index. - For index 6, |6 - 5| <= k and nums[5] == key, so 6 is a k-distant index.Thus, we return [1,2,3,4,5,6] which is sorted in increasing order.
Example 2:
Input: nums = [2,2,2,2,2], key = 2, k = 2 Output: [0,1,2,3,4] Explanation: For all indices i in nums, there exists some index j such that |i - j| <= k and nums[j] == key, so every index is a k-distant index. Hence, we return [0,1,2,3,4].
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1000key is an integer from the array nums.1 <= k <= nums.lengthThis approach iterates over each element in the array and checks for every index if it's k-distant to any key index. It ensures all indices within k-distant range are added. Although straightforward, this method might involve redundant checks leading to inefficiency, especially with larger arrays.
The solution uses a nested loop: the outer loop traverses through each element, while the inner loop checks for any key occurrence within k distance. If the condition is met, the index is added to a result set, which guarantees unique entries. Finally, the set is sorted to adhere to the problem's requirement.
C
Time Complexity: O(n^2), where n is the number of elements in nums.
Space Complexity: O(n) for storing result indices.
This approach optimizes the process by initially identifying all positions where the key is present. Then, it loops over each index and checks if it falls within the k-distant range of any key index, using a sorted check on these indices.
The solution begins by capturing indices of the key in a list. It ensures only one pass through nums to generate the indices list. A separate pass checks all nums entries for k-distance to any key index.
C++
Time Complexity: O(n * m) where m is the count of key indices. Worst case, it approaches O(n^2).
Space Complexity: O(n) for the result set and key indices storage.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the number of elements in nums. |
| Optimized Solution Using Key Index Tracking | Time Complexity: O(n * m) where m is the count of key indices. Worst case, it approaches O(n^2). |
ALL NODES DISTANCE K IN BINARY TREE | PYTHON | LEETCODE # 863 • Cracking FAANG • 12,524 views views
Watch 9 more video solutions →Practice Find All K-Distant Indices in an Array with our built-in code editor and test cases.
Practice on FleetCode