Find All K-Distant Indices in an Array - Solution & Explanation
Problem Statement
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] <= 1000keyis an integer from the arraynums.1 <= k <= nums.length
Approach Overview
Problem Overview: You are given an integer array nums, a target value key, and an integer k. An index i is considered k-distant if there exists some index j where nums[j] == key and |i - j| ā¤ k. The task is to return all such indices in increasing order.
Approach 1: Brute Force Check (O(nĀ²) time, O(1) extra space)
The direct solution checks every index and verifies whether a valid key exists within distance k. For each index i, iterate through all indices j and check two conditions: nums[j] == key and |i - j| ā¤ k. If both hold, mark i as a valid k-distant index. This approach relies purely on nested iteration over the array, so the worst-case runtime becomes O(nĀ²). Space usage stays O(1) excluding the result list. While inefficient for large arrays, this method clearly demonstrates the definition of a k-distant index and is useful as a baseline implementation.
Approach 2: Optimized Key Index Tracking (O(n) time, O(1) extra space)
A more efficient strategy focuses only on positions where the value equals key. When you encounter an index j such that nums[j] == key, every index in the range [j - k, j + k] is valid. Clamp this range to array bounds using max(0, j - k) and min(n - 1, j + k). The challenge is avoiding duplicates when multiple key indices produce overlapping ranges.
Track the last index already added to the result. When processing a new key position, start inserting from max(last_added + 1, j - k) instead of j - k. This guarantees each index is added only once while scanning the array. Since every element is processed at most once, the runtime becomes O(n) with constant extra space besides the output. Conceptually, this behaves like expanding coverage intervals around key positions while iterating the array, a pattern often seen in two pointers and range-merging problems.
Recommended for interviews: Start by describing the brute force definition to show you understand the problem constraints. Then move quickly to the optimized key-index tracking solution. Interviewers typically expect the O(n) scan because it eliminates redundant checks and handles overlapping ranges cleanly.
Approach 1: Brute Force Approach
This 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.
Complexity
Time Complexity: O(n^2), where n is the number of elements in nums.
Space Complexity: O(n) for storing result indices.
Approach 2: Optimized Solution Using Key Index Tracking
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.
Complexity
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 3: Enumeration
We enumerate the index i in the range [0, n), and for each index i, we enumerate the index j in the range [0, n). If |i - j| leq k and nums[j] = key, then i is a K-nearest neighbor index. We add i to the answer array, then break the inner loop and enumerate the next index i.
The time complexity is O(n^2), where n is the length of the array nums. The space complexity is O(1).
Approach 4: Preprocessing + Binary Search
We can preprocess to get the indices of all elements equal to key, recorded in the array idx. All index elements in the array idx are sorted in ascending order.
Next, we enumerate the index i. For each index i, we can use binary search to find elements in the range [i - k, i + k] in the array idx. If there are elements, then i is a K-nearest neighbor index. We add i to the answer array.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
Approach 5: Two Pointers
We enumerate the index i, and use a pointer j to point to the smallest index that satisfies j geq i - k and nums[j] = key. If j exists and j leq i + k, then i is a K-nearest neighbor index. We add i to the answer array.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Complexity Comparison
| 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). |
| Enumeration | ā |
| Preprocessing + Binary Search | ā |
| Two Pointers | ā |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Check | O(nĀ²) | O(1) | Useful for understanding the definition of k-distant indices or when array size is very small |
| Optimized Key Index Tracking | O(n) | O(1) | Best general solution. Efficiently handles overlapping ranges and large arrays |
Video Solution
Find All K-Distant Indices in an Array | Easy | Leetcode 2200 | codestorywithMIK ā¢ codestorywithMIK ā¢ 6,525 views views
Watch 9 more video solutions āFrequently Asked Questions
Is Find All K-Distant Indices in an Array easy or hard?
Find All K-Distant Indices in an Array Python/Java solution
How to solve Find All K-Distant Indices in an Array in O(n)?
What is the best approach for Find All K-Distant Indices in an Array?
Is Find All K-Distant Indices in an Array asked at Google/Amazon/Meta?
What data structure is used in Find All K-Distant Indices in an Array?
What is the time complexity of Find All K-Distant Indices in an Array?
Ready to solve this problem?
Practice Find All K-Distant Indices in an Array with our built-in code editor and test cases.
Practice on FleetCode