Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

An index qualifies if at least one occurrence of key lies within distance k. The reference solution checks this existential condition directly after collecting the key's positions.

Approach

First store every index whose value equals key. Then scan all array indices in increasing order and compare each with the stored positions. Append an index as soon as an absolute distance is at most k, then stop its inner scan. Breaking after the first match prevents duplicates when several key occurrences cover the same index, and the outer scan makes the output sorted. Distance exactly k is included.

class Solution:
    def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
        n = len(nums)
        pos = set()

        for i in range(n):
            if nums[i] == key:
                pos.add(i)

        res = []

        for i in range(n):
            for p in pos:
                if abs(p - i) <= k:
                    res.append(i)
                    break

        return res

Complexity analysis

Let n = nums.length, q be the number of occurrences of key, and o the output size. Time: O(n + n * q). Auxiliary space: O(q) for key positions; the returned list uses O(o) space.