Find All K-Distant Indices in an Array

Find All K-Distant Indices in an Array

What is this problem about?

In the Find All K-Distant Indices in an Array coding problem, you are given an array nums, a target value, and an integer k. An index i is "k-distant" if there exists any index j such that nums[j] == target and the absolute distance $|i - j| \le k$. You need to return all such "good" indices in increasing order.

Why is this asked in interviews?

This "Easy" difficulty question is used by Meta and Amazon to test a candidate's ability to handle range overlaps efficiently. While a brute-force $O(N^2)$ check is possible, it's not optimal. It evaluation whether you can identify the Two Pointers interview pattern or a "Sliding Window" of impact to solve the problem in a single linear pass.

Algorithmic pattern used

This is a Linear Scan and Range Merging problem.

1. Identify all indices j where nums[j] == target.
2. Each such j makes the range $[j-k, j+k]$ valid.
3. You want to find the union of all these ranges.
4. Use a pointer last_covered to keep track of the largest index added to the result to avoid duplicates and ensure the output is sorted.

Example explanation

nums = [3, 4, 9, 1, 3, 9, 5], target = 9, k = 1.

1. Target 9 found at index 2. Range: [1, 3]. Add indices 1, 2, 3 to result. last_covered = 3.
2. Target 9 found at index 5. Range: [4, 6].
3. Since last_covered < 4, start adding from 4. Add 4, 5, 6 to result. Result: [1, 2, 3, 4, 5, 6].

Common mistakes candidates make

• Double-counting: Adding the same index multiple times if it is near two different target elements.
• Sorting at the end: Generating all possible $(i, j)$ pairs and then sorting the result, which is less efficient than a single ordered pass.
• Off-by-one: Not correctly bounding the range $[j-k, j+k]$ within the array limits $[0, n-1]$.

Interview preparation tip

When you have multiple overlapping "regions of influence" (like the $k$-distance here), avoid a nested loop. Instead, track the "frontier" of your progress. This is a common theme in Interval interview patterns.