We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find All K-Distant Indices in an Array

Number: 2320

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given an integer array nums, an integer key, and an integer k, find all indices i in nums for which there exists at least one index j such that |i - j| <= k and nums[j] equals key. Return the list of these indices sorted in increasing order.

Key Insights

  • Identify all indices where the element equals key.
  • For each discovered key index, mark all indices within the range [j - k, j + k] as valid.
  • Use a set to avoid duplicate indices when ranges overlap.
  • Finally, convert the set to a sorted list to satisfy the increasing order requirement.

Space and Time Complexity

Time Complexity: O(n * k) in the worst-case when many indices are keys (with n as the length of nums)
Space Complexity: O(n) for storing the set of valid indices and eventually the result list

Solution

We first iterate over the array to gather all indices where nums equals key. For each such index j, we then iterate from max(0, j - k) to min(n - 1, j + k) and add these indices to a set. This ensures that even if ranges overlap, we add unique indices only. After processing all key indices, we sort the set into a list and return it. The algorithm primarily uses a set for uniqueness and a couple of loops that traverse the array and defined ranges based on k.

Code Solutions

# Define the function to find k-distant indices
def findKDistantIndices(nums, key, k):
    # Set to store unique valid indices
    valid_indices = set()
    n = len(nums)
    
    # Iterate over each index in nums
    for j in range(n):
        # If the element equals key, then mark all indices within distance k
        if nums[j] == key:
            # Determine the start and end index for valid range ensuring bounds
            start = max(0, j - k)
            end = min(n - 1, j + k)
            # Add each valid index to the set
            for i in range(start, end + 1):
                valid_indices.add(i)
    
    # Convert the set to a sorted list and return
    return sorted(list(valid_indices))

# Example usage
print(findKDistantIndices([3, 4, 9, 1, 3, 9, 5], 9, 1))
← Back to All Questions