Find All K-Distant Indices in an Array — Editorial

Opening the reading…

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.

Each key occurrence contributes an interval, and the answer is their union.

Approach

Store 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.

Scan 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.

For 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.

Set 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.

Scan 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.

Return 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

MEASURE	BOUND	WHY
Time	O(n^2) worst case	The outer scan and final collection each visit n positions. A key occurrence can mark up to n positions, and with many key occurrences those marking ranges can overlap and still be revisited, so the total work can reach n x n.
Space	O(n) extra	The mark array stores one boolean per input index, while ans is required output and is excluded from the extra-space bound. The working memory remains O(n) even when key occurrences are sparse or when every position equals key.

Here n is the length of nums. The input value k does not need a separate symbol because the worst-case bounds are expressed using n.

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

CPPMark every interval generated by a key occurrence, then collect marked indices in order.

#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.

CPPKeep one forward-only pointer to the first key occurrence that can still cover the current index.

#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.