Scale Engineer

Find All K-Distant Indices in an Array

Easy
#2004Time: 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: 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.
Patterns
Two Pointers
Data structures
Array

Prompt

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:

nums[2] == key

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

4 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem