Find All K-Distant Indices in an Array

Problem Description

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.

Key Insights

• Identify all indices of nums where nums[j] == key.
• For each index i, check if there exists an index j within the range [i-k, i+k] that equals key.
• Collect and return all valid indices in a sorted manner.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The algorithm uses a two-step approach. First, we traverse the nums array to find all indices where nums[j] matches key. Next, we determine the k-distant indices by iterating through the array again and checking if there is any index j that satisfies the condition |i - j| <= k. We can utilize a set to collect the valid indices to avoid duplicates.

Code Solutions