Find All K-Distant Indices in an Array

Language Options

Problem Description

Welcome to the whimsical world of arrays, where numbers frolic and play! Today, we have a delightful challenge: Find All K-Distant Indices in an Array. Imagine you’re at a party, and you want to find all your friends who are within a certain distance from you. But instead of friends, we have indices, and instead of distance, we have a magical number called k.

In this problem, you’re given an array of integers, a key integer, and a distance k. Your task is to find all indices in the array that are at most k distance away from any index where the value is equal to the key. Sounds simple, right? Just like finding your lost sock in a pile of laundry—except this time, you have to do it with numbers!

Code Solution


class Solution {
  public List findKDistantIndices(int[] nums, int key, int k) {
    final int n = nums.length;
    List ans = new ArrayList<>();

    for (int i = 0, j = 0; i < n; ++i) {
      while (j < n && (nums[j] != key || j < i - k))
        ++j;
      if (j == n)
        break;
      if (Math.abs(i - j) <= k)
        ans.add(i);
    }

    return ans;
  }
}

Approach Explanation

The code works by iterating through each index of the array. For each index i, it checks if there exists an index j such that nums[j] equals the key and j is within the range of i - k. If such an index exists, it adds i to the result list. The inner while loop ensures that we efficiently find the first valid index j without unnecessary checks.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the array.
Space Complexity	O(m), where m is the number of indices that are added to the result list.

Real-World Example

Imagine you’re at a concert, and you want to find all the people who are within a certain distance from your favorite singer (the key). If the singer is at index 5, and you can only tolerate a distance of 2, you’d want to find all the fans at indices 3, 4, 5, 6, and 7. This problem is just like that—finding all the indices that are close enough to the key!