Find All K-Distant Indices in an Array

EASY

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.

Example 1:

Input: nums = [3,4,9,1,3,9,5], key = 9, k = 1
Output: [1,2,3,4,5,6]
Explanation: Here, nums[2] == key and nums[5] == key.
- For index 0, |0 - 2| > k and |0 - 5| > k, so there is no j where |0 - j| <= k and nums[j] == key. Thus, 0 is not a k-distant index.
- For index 1, |1 - 2| <= k and nums[2] == key, so 1 is a k-distant index.
- For index 2, |2 - 2| <= k and nums[2] == key, so 2 is a k-distant index.
- For index 3, |3 - 2| <= k and nums[2] == key, so 3 is a k-distant index.
- For index 4, |4 - 5| <= k and nums[5] == key, so 4 is a k-distant index.
- For index 5, |5 - 5| <= k and nums[5] == key, so 5 is a k-distant index.
- For index 6, |6 - 5| <= k and nums[5] == key, so 6 is a k-distant index.
Thus, we return [1,2,3,4,5,6] which is sorted in increasing order.

Example 2:

Input: nums = [2,2,2,2,2], key = 2, k = 2
Output: [0,1,2,3,4]
Explanation: For all indices i in nums, there exists some index j such that |i - j| <= k and nums[j] == key, so every index is a k-distant index. 
Hence, we return [0,1,2,3,4].

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
key is an integer from the array nums.
1 <= k <= nums.length

Approaches

Checkout 4 different approaches to solve Find All K-Distant Indices in an Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force

This approach directly translates the problem definition into code. It iterates through every possible index i in the array and, for each i, performs a full scan of the array to check if it satisfies the k-distant condition.

Algorithm

Initialize an empty list result.
Loop with index i from 0 to nums.length - 1.
Inside the loop, start another loop with index j from 0 to nums.length - 1.
Check if nums[j] == key and Math.abs(i - j) <= k.
If the condition is true, add i to result and break the inner loop (since we only need one such j to exist).
Return result.

For each index i from 0 to n-1, we need to determine if it's a k-distant index. To do this, we perform another full scan of the array using an index j. In this inner scan, we look for an index j where nums[j] is equal to the key and the absolute difference |i - j| is less than or equal to k. If such a j is found, we confirm that i is a k-distant index. We then add i to our result list and can immediately stop searching for this i (by breaking the inner loop) and move to the next index i+1. Since we iterate i in increasing order, the resulting list will naturally be sorted.

class Solution {
    public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
        List<Integer> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (nums[j] == key && Math.abs(i - j) <= k) {
                    result.add(i);
                    break; // Found a valid j, move to the next i
                }
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of the `nums` array. The outer loop runs N times, and for each iteration, the inner loop can run up to N times.Space Complexity: O(N) in the worst case for storing the result list, where N is the number of elements in `nums`. This occurs if all indices are k-distant.

Pros and Cons

Pros:

Very simple to understand and implement.
Directly follows the problem statement.

Cons:

Highly inefficient due to nested loops, leading to a quadratic time complexity.
Likely to result in a 'Time Limit Exceeded' error on platforms with stricter time limits for larger inputs.

Code Solutions

Checking out 3 solutions in different languages for Find All K-Distant Indices in an Array. Click on different languages to view the code.

class Solution {
public
  List<Integer> findKDistantIndices(int[] nums, int key, int k) {
    int n = nums.length;
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (Math.abs(i - j) <= k && nums[j] == key) {
          ans.add(i);
          break;
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Find All K-Distant Indices in an Array

Patterns:

Two Pointers

Data Structures:

Array