LeetCode 2200 - Find All K-Distant Indices in an Array

The problem requires identifying all indices in an array nums that are "k-distant" from at least one occurrence of a given value key.

leetcodeeasyarraytwo-pointers

LeetCode Problem 2200

Difficulty: 🟢 Easy
Topics: Array, Two Pointers

Solution

Problem Understanding

The problem requires identifying all indices in an array nums that are "k-distant" from at least one occurrence of a given value key. In other words, for each index i, we need to determine whether there exists some index j such that nums[j] == key and the distance between i and j is at most k. The output should be a sorted list of all such indices.

The input consists of a 0-indexed integer array nums, an integer key that is guaranteed to exist in nums, and an integer k which is at least 1 and at most the length of nums. The constraints (nums.length <= 1000) indicate that a solution with quadratic time complexity may be acceptable, but we can optimize further.

Important edge cases include situations where every element equals key, where k is equal to the array length, or where key occurs only at the boundaries. The problem guarantees non-empty arrays and that key exists in nums, which simplifies some validation.

Approaches

Brute Force Approach

A brute-force approach iterates over each index i in nums and, for each i, scans the subarray nums[max(0, i-k) : min(len(nums)-1, i+k)] to check if any element equals key. If such an element exists, i is added to the result. This approach is correct because it directly implements the definition of a k-distant index, but it requires checking up to 2k+1 elements for every index, resulting in a worst-case time complexity of O(n * k).

Optimal Approach

A more efficient approach leverages the fact that key positions can be precomputed. First, collect all indices j where nums[j] == key. Then, iterate over these positions and mark all indices from max(0, j-k) to min(n-1, j+k) as k-distant. This avoids redundant checks and ensures each index is considered at most once. Sorting is optional because the marking can be done in order from left to right, guaranteeing sorted output.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * k) O(n) Checks every index against the k-distance window of all indices
Optimal O(n) O(n) Precomputes key positions and directly marks k-distant indices

Algorithm Walkthrough

  1. Initialize an empty boolean array isKDistant of length n (length of nums) to track which indices are k-distant.
  2. Iterate over the array nums to collect all indices j such that nums[j] == key.
  3. For each key index j, calculate the start and end of the k-distant range: start = max(0, j - k) and end = min(n - 1, j + k).
  4. Mark all indices from start to end inclusive as k-distant in isKDistant.
  5. After processing all key indices, iterate over isKDistant and collect all indices marked True into a result array.
  6. Return the result array, which is already sorted because indices were processed in increasing order.

Why it works: By marking ranges around each occurrence of key, the algorithm ensures that every index that satisfies the k-distant condition is included exactly once. The left-to-right iteration preserves the sorted order.

Python Solution

from typing import List

class Solution:
    def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
        n = len(nums)
        is_k_distant = [False] * n
        
        for j, num in enumerate(nums):
            if num == key:
                start = max(0, j - k)
                end = min(n - 1, j + k)
                for i in range(start, end + 1):
                    is_k_distant[i] = True
        
        result = [i for i, val in enumerate(is_k_distant) if val]
        return result

The implementation first initializes a boolean array to track k-distant indices. It then iterates over each element of nums, marking the range around each key index. Finally, it collects all marked indices into a list, producing the sorted output.

Go Solution

func findKDistantIndices(nums []int, key int, k int) []int {
    n := len(nums)
    isKDistant := make([]bool, n)
    
    for j, num := range nums {
        if num == key {
            start := j - k
            if start < 0 {
                start = 0
            }
            end := j + k
            if end >= n {
                end = n - 1
            }
            for i := start; i <= end; i++ {
                isKDistant[i] = true
            }
        }
    }
    
    result := []int{}
    for i, val := range isKDistant {
        if val {
            result = append(result, i)
        }
    }
    return result
}

In Go, we explicitly handle the bounds of slices and use the built-in append function to collect results. The boolean slice isKDistant mirrors the Python approach.

Worked Examples

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

Step Key Index Start End Marked Indices
1 2 1 3 1,2,3
2 5 4 6 1,2,3,4,5,6

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

Example 2: nums = [2,2,2,2,2], key = 2, k = 2

Step Key Index Start End Marked Indices
1 0 0 2 0,1,2
2 1 0 3 0,1,2,3
3 2 0 4 0,1,2,3,4
4 3 1 4 0,1,2,3,4
5 4 2 4 0,1,2,3,4

Result: [0,1,2,3,4]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Iterate over nums once and mark ranges; each index marked at most once
Space O(n) Boolean array to track k-distant indices

The solution is linear because although marking ranges may seem like nested iteration, each index is processed a constant number of times relative to the number of key occurrences, and the array length is bounded.

Test Cases

# Provided examples
assert Solution().findKDistantIndices([3,4,9,1,3,9,5], 9, 1) == [1,2,3,4,5,6]  # example 1
assert Solution().findKDistantIndices([2,2,2,2,2], 2, 2) == [0,1,2,3,4]      # example 2

# Edge and boundary cases
assert Solution().findKDistantIndices([1], 1, 1) == [0]                         # single element
assert Solution().findKDistantIndices([1,2,3,4,5], 3, 2) == [0,1,2,3,4]       # key in middle, k large enough
assert Solution().findKDistantIndices([1,2,3,4,5], 5, 1) == [3,4]             # key at end
assert Solution().findKDistantIndices([1,2,3,4,5], 1, 1) == [0,1]             # key at start
assert Solution().findKDistantIndices([1,1,1,1,1], 1, 1) == [0,1,2,3,4]       # all elements are key
Test Why
Single element Smallest input size, key is only element
Key in middle Tests range expansion to both sides
Key at end/start Tests boundary handling
All elements are key All indices should be included

Edge Cases

  1. Single element array: If the array has only one element, and it equals the key, the only index is trivially k-distant. Implementation handles this with normal range calculation using max and min.
  2. Key at the start or end: When key appears at boundaries, the calculated start or end of the range may go out of bounds. Using max(0, j-k) and min(n-1, j+k) correctly clips the range to valid indices.
  3. All elements are key: In this case, every index is k-distant. The boolean array marking ensures all