algoadvance

The problem is as follows:

You are given a 0-indexed integer array nums and two integers key and k. A k-distant index in nums is an index i such that there exists at least one index j in nums where nums[j] == key and the absolute difference between i and j is less than or equal to k.

Return a list of all k-distant indices sorted in increasing order.

Clarifying Questions

1. What are the constraints?
   • Is the length of nums constrained to a specific range?
   • Can key be any integer value, and will k always be non-negative?
2. Examples
   • nums = [3, 4, 9, 1, 3, 9, 5], key = 9, k = 2 should return [1, 2, 3, 4, 5, 6].
   • Is it guaranteed that nums has at least one occurrence of key?

Strategy

1. Identify key Indices: First, go through the array to find all indices j where nums[j] == key.
2. Mark k-Distant Indices: For each such index j, mark all indices i in the range [j - k, j + k] as valid k-distant indices.
3. Collect and Return Results: Collect all the unique k-distant indices and return them sorted.

Code

def findKDistantIndices(nums, key, k):
    key_indices = []
    n = len(nums)
    
    # Finding all the indices where nums[j] == key
    for idx in range(n):
        if nums[idx] == key:
            key_indices.append(idx)
    
    k_distant_indices = set()
    
    # For each key index j, mark the indices i in the range [j - k, j + k]
    for j in key_indices:
        start = max(0, j - k)
        end = min(n - 1, j + k)
        for i in range(start, end + 1):
            k_distant_indices.add(i)
    
    # Return the sorted list of k-distant indices
    return sorted(k_distant_indices)

# Example Usage
nums = [3, 4, 9, 1, 3, 9, 5]
key = 9
k = 2
print(findKDistantIndices(nums, key, k))
# Output: [1, 2, 3, 4, 5, 6]

Time Complexity

• O(n): Finding all key indices involves a single pass through the nums array.
• O(m * k): Marking k-distant indices is proportional to the number of key occurrences (let’s call it m), and for each key occurrence we need to mark up to 2k + 1 indices.
• O(n log n): Sorting the k-distant indices.

Therefore, in the worst case, the time complexity is O(n + m * k + n log n). Given typical constraints, this solution should be efficient enough for large inputs.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?