[Leetcode] 2200. Find All K-Distant Indices in an Array

https://leetcode.com/problems/find-all-k-distant-indices-in-an-array/description/?envType=daily-question&envId=2025-06-24

initial

v straightforward. be careful with the limits of pointer j. I reversed min and max in that for range loop initially but we should get max of 0 and i-k cuz if i-k goes negative, we need to get 0

class Solution:
    def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
        length = len(nums)
        visited= [False for _ in range(length)]
        for i in range(length):
            num=nums[i]
            if num==key:
                for j in range(max(0,i-k),min(length,i+k+1)):
                    if not visited[j]:
                        visited[j]=True
        ans = []
        for i in range(length):
            if visited[i]:
                ans.append(i)
        return ans

sol

we are iterating k times of the original nums list. We can actually just iterate once - one pass

def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
    result = []
    n = len(nums)
    i, j = 0, 0 # i iterates through nums, j tracks the next candidate k-distant index
    
    # i iterates through all potential key locations
    while i < n:
        if nums[i] == key:
            # When a key is found at index 'i':
            # Calculate the starting point of its k-distant range: max(i - k, 0)
            # Crucially, 'j' is advanced to ensure it never goes backward.
            # This handles overlapping ranges efficiently without re-processing.
            j = max(i - k, j) # The actual starting point for marking for this 'key'
                              # is the max of (i-k) and the current 'j' position.
                              # This means 'j' only ever moves forward.
            
            # Mark all indices from 'j' up to (i + k) as k-distant
            # The loop condition j <= i + k ensures we cover the range for current 'key' at 'i'
            # The j < n ensures we don't go out of bounds
            while j < n and j <= i + k:
                result.append(j)
                j += 1 # Move 'j' to the next index to be considered
        i += 1 # Move 'i' to find the next potential 'key'
    
    return result

complexity

n time
n space