2200. Find All K-Distant Indices in an Array

EasyView on LeetCode

Array

Time: O(n²)

Space: O(n)

Problem Overview

Index i is k-distant if some index j with |i-j| <= k has nums[j] == key.

Intuition

Index i is k-distant if some index j with |i-j| <= k has nums[j] == key. Equivalently, every occurrence of key marks all indices within distance k. Collect marked indices in sorted order.

Algorithm

1For each index i from 0 to n-1:
2Check if any j in [max(0,i-k), min(n-1,i+k)] has nums[j] == key.
3If yes, append i to the answer list.
4Return the list (indices are naturally increasing).

Example Walkthrough

Input: nums = [3,4,9,5,7,1,9], key = 9, k = 1

1.9 at indices 2 and 6. Within k=1 of index 2: 1,2,3. Of index 6: 5,6.

Output: [1, 2, 3, 4, 5, 6]

Common Pitfalls

•Condition is existence of key within distance k — not nums[i] itself.
•Use inclusive bounds on j: |i-j| <= k.
•O(n*k) or O(n^2) is fine for typical constraints.

2200.cs

// Approach: For each key occurrence in nums, mark all i within distance k; skip already-added indices.
// Time: O(n²) Space: O(n)

public class Solution
{
    public IList<int> FindKDistantIndices(int[] nums, int key, int k)
    {
        // The length of the array 'nums'
        int n = nums.Length;
        // Initialize the list to store the answer
        List<int> kDistantIndices = new List<int>();
        // Iterate over all elements of 'nums'
        for (int i = 0; i < n; ++i)
        {
            // Check elements again to find indices within distance 'k' of 'key' in 'nums'
            for (int j = 0; j < n; ++j)
            {
                // If the absolute difference between indices 'i' and 'j' is less than or equal to 'k'
                // and the current element nums[j] is equal to 'key', the condition is met
                if (Math.Abs(i - j) <= k && nums[j] == key)
                {
                    // Add the current index 'i' to the list of results
                    kDistantIndices.Add(i);
                    // Break from the inner loop since we've found the key at this 'i' index
                    break;
                }
            }
        }
        // Return the list of indices that are within distance 'k' from the elements equal to 'key'
        return kDistantIndices;
    }
}

Was this solution helpful?