🌋 Find All K-Distant Indices in an Array – LeetCode 2200 (C++ | Python | JavaScript)

👋 Introduction

Hey, algorithm adventurers! 🔍✨

Today we’re diving into a slick little indexing challenge from LeetCode — 2200: Find All K-Distant Indices in an Array. At first glance, it seems simple, but crafting an efficient solution requires a clever greedy strategy using pointers.

Let’s break it down and uncover the logic behind this clean and optimal approach. 💡

🧠 Problem Summary

You're given:

• An integer array nums
• An integer key
• An integer k

An index i is called k-distant if there's at least one index j such that:

• |i - j| <= k and
• nums[j] == key

Your task is to return all such indices in increasing order.

---

🧩 Intuition

The goal is to find all indices i such that within a window of distance k from i, there's at least one index j where nums[j] == key.

Instead of checking every index i against all j, we can do the opposite:

1. For each index j where nums[j] == key, add all indices i from [j - k, j + k] to a result set.
2. This way we cover all valid i that are within distance k from a key position.
3. Use a start pointer to avoid re-adding previous indices.

This approach is clean, greedy, and linear.

---

🧮 C++ Code

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

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

                while(start<=right){
                    if (start>=left) ans.push_back(start);
                    start++;
                }
            }
        }

        return ans;
    }
};

📝 Key Notes:

• We linearly process the array.
• The variable start ensures we never re-check old indices.
• Time complexity is O(n), space is O(1) apart from the output.

---

💻 JavaScript Code

var findKDistantIndices = function(nums, key, k) {
    const ans = [];
    const n = nums.length;
    let start = 0;

    for (let i = 0; i < n; i++) {
        if (nums[i] === key) {
            const left = Math.max(0, i - k);
            const right = Math.min(n - 1, i + k);

            while (start <= right) {
                if (start >= left) ans.push(start);
                start++;
            }
        }
    }

    return ans;
};

---

🐍 Python Code

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

        for i in range(n):
            if nums[i] == key:
                left = max(0, i - k)
                right = min(n - 1, i + k)

                while start <= right:
                    if start >= left:
                        ans.append(start)
                    start += 1

        return ans

---

✅ Final Thoughts

This problem highlights a great case for a greedy + pointer approach. By directly jumping to key positions and expanding outwards, we efficiently reduce unnecessary comparisons.

If you found this helpful, drop a ❤️ and follow along for more breakdowns and clean patterns!

Happy coding! 🚀

Comments

[Anna kowoski]

Well Explained!

[Om Shree]

Thanks Anna