Find All K-Distant Indices in an Array - Video Solutions
Find All K-Distant Indices in an Array | Easy | Leetcode 2200 | codestorywithMIK
Find All K-Distant Indices in an Array - Video Solution
Watch 10 video solutions for Find All K-Distant Indices in an Array, a easy level problem involving Array, Two Pointers. This walkthrough by codestorywithMIK has 6,525 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |