Find All K-Distant Indices in an Array

Intuitionturning 'there exists a key nearby' into covered intervals

An index i is valid when at least one occurrence of key lies between i - k and i + k. Equivalently, each key occurrence at position i covers an interval of candidate indices from max(0, i - k) through min(n - 1, i + k). The answer is the union of all these intervals, not a separate copy of an interval for every occurrence.

Use a boolean mark for each array index. Whenever nums[i] equals key, mark every index in its covered interval. Overlapping intervals cause no problem: marking an already-marked position leaves the same answer. After all key occurrences have been processed, scan the marks from left to right and append exactly the marked indices, which automatically gives increasing order.

Approach

1. 1Store n as nums.size() and create mark with n false entries, because every possible answer index needs one place to record whether any key occurrence reaches it.
2. 2Scan every index i from 0 through n - 1 and check whether nums[i] equals key, because non-key positions do not create a new distance interval.
3. 3For each key occurrence, calculate the interval from max(0, i - k) to min(n - 1, i + k), because the mathematical interval may extend outside the array and those invalid positions must not be visited.
4. 4Set mark[j] to true for every j in that interval, because one nearby key is enough to make j valid and repeated marking safely handles overlapping intervals.
5. 5Scan mark from left to right and append each true index to ans, because this final order is increasing and avoids emitting the same index once per nearby key occurrence.
6. 6Return ans after the scan, because all key-generated intervals have already been combined in mark.

Complexitythe marking method trades working memory for simple interval handling

Annotated solutionC++ · interval marking · direct and easy to verify

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findKDistantIndices(vector<int>& nums, int key, int k) {
        int n = nums.size();
        vector<bool> mark(n, false);

        for (int i = 0; i < n; ++i) {
            if (nums[i] == key) {
                int left = max(0, i - k);
                int right = min(n - 1, i + k);
                for (int j = left; j <= right; ++j) {
                    mark[j] = true;
                }
            }
        }

        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            if (mark[i]) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

The two boundary expressions are the important placement details. Using max(0, i - k) prevents a negative array index on the left, while min(n - 1, i + k) prevents a position beyond the last element on the right. The final scan is separate from marking so overlapping intervals cannot create duplicate entries and the required increasing order comes for free.

The monotonic pointer alternativean O(n)-time, O(1)-extra-space optimisation

You can avoid mark by scanning candidate indices from left to right and maintaining the first key occurrence that has not fallen too far left. As i increases, the lower boundary i - k never moves backward, so the pointer to the first usable key also never moves backward. If that key is at most i + k, index i is valid; otherwise no later key can help this i.

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findKDistantIndices(vector<int>& nums, int key, int k) {
        int n = nums.size();
        vector<int> ans;
        int firstKey = 0;

        for (int i = 0; i < n; ++i) {
            while (firstKey < n &&
                   (nums[firstKey] != key || firstKey < i - k)) {
                ++firstKey;
            }

            if (firstKey < n && firstKey <= i + k) {
                ans.push_back(i);
            }
        }

        return ans;
    }
};

This version is an optimisation, not merely a different arrangement. The pointer advances at most n times, and the outer loop also advances n times, giving O(n) time and O(1) extra space besides the returned vector. The marking version is often easier to reason about, while this version is useful when avoiding an auxiliary array matters.

Common mistakestwo boundary and duplication traps