#2200

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Find All K-Distant Indices in an Array

Identify all indices in an array that are within k distance of elements equal to the given key using two-pointer scanning.

array two pointers

Problem Statement

Given a 0-indexed integer array nums and two integers key and k, an index i is called k-distant if there exists at least one index j such that |i - j| <= k and nums[j] == key. Return all k-distant indices in increasing order.

For example, with nums = [3,4,9,1,3,9,5], key = 9, and k = 1, the output is [1,2,3,4,5,6]. Every index within distance 1 of any 9 in the array is included in the result.

Examples

Example 1

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

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

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]

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

Solution Approach

Locate Key Indices

Iterate through nums to identify all indices where nums[i] == key. Store these indices to facilitate two-pointer scanning and distance checks.

Two-Pointer Scan for k-Distance

Use two pointers to iterate over nums and the list of key indices. For each array index, check if it falls within k distance of any key index. Add qualifying indices to the result list while maintaining sorted order.

Optimize and Return

Avoid duplicates by ensuring each index is added only once. Return the final list of k-distant indices, which is already sorted due to sequential scanning.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) since each index is scanned once and checked against nearby key positions. Space complexity is O(1) extra beyond the input, as the output list is required by the problem.

What Interviewers Usually Probe

Check if the solution handles multiple key occurrences correctly.
Ask whether the indices list is correctly sorted without extra sorting steps.
Probe handling of edge indices near array boundaries.

Common Pitfalls or Variants

Common pitfalls

Failing to include all indices within k distance of multiple key occurrences.
Adding duplicate indices when k ranges overlap for consecutive keys.
Incorrectly handling indices at the start or end of the array.

Follow-up variants

Return k-distant indices in descending order instead of increasing.
Count the total number of k-distant indices instead of listing them.
Find indices distant from multiple different keys simultaneously.

FAQ

What is a k-distant index in this problem?

A k-distant index is any array index i such that there exists an index j with nums[j] equal to the key and |i - j| <= k.

Can this be solved without two-pointer scanning?

Yes, but two-pointer scanning with invariant tracking ensures O(n) time and handles overlapping ranges efficiently.

What happens if key occurs multiple times consecutively?

All indices within k distance from each occurrence are included, but duplicates are avoided by tracking additions carefully.

Is the output always sorted?

Yes, scanning the array sequentially ensures indices are added in increasing order.

Does GhostInterview handle arrays of length up to 1000 efficiently?

Yes, it uses constant extra space beyond the output and performs a linear scan, keeping runtime optimal for arrays up to 1000 elements.

terminal

Solution

Solution 1: Enumeration

We enumerate the index $i$ in the range $[0, n)$, and for each index $i$, we enumerate the index $j$ in the range $[0, n)$. If $|i - j| \leq k$ and $nums[j] = key$, then $i$ is a K-nearest neighbor index. We add $i$ to the answer array, then break the inner loop and enumerate the next index $i$.

1

2

3

4

5

6

7

8

class Solution:
    def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
        ans = []
        n = len(nums)
        for i in range(n):
            if any(abs(i - j) <= k and nums[j] == key for j in range(n)):
                ans.append(i)
        return ans

Solution 2: Preprocessing + Binary Search

We can preprocess to get the indices of all elements equal to $key$, recorded in the array $idx$. All index elements in the array $idx$ are sorted in ascending order.

1

2

3

4

5

6

7

8

class Solution:
    def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
        ans = []
        n = len(nums)
        for i in range(n):
            if any(abs(i - j) <= k and nums[j] == key for j in range(n)):
                ans.append(i)
        return ans

Solution 3: Two Pointers

We enumerate the index $i$, and use a pointer $j$ to point to the smallest index that satisfies $j \geq i - k$ and $nums[j] = key$. If $j$ exists and $j \leq i + k$, then $i$ is a K-nearest neighbor index. We add $i$ to the answer array.

1

2

3

4

5

6

7

8

class Solution:
    def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
        ans = []
        n = len(nums)
        for i in range(n):
            if any(abs(i - j) <= k and nums[j] == key for j in range(n)):
                ans.append(i)
        return ans

Continue Practicing

#2234 maximum total beauty of the gardens #2161 partition array according to given pivot #2149 rearrange array elements by sign