Find All K-Distant Indices in an Array

Easy

Asked by:

26 views

Topics:

Arrays

You are given a 0-indexed integer array nums and two integers key and k. A k-distant index is an index i of nums for which there exists at least one index j such that |i - j| <= k and nums[j] == key.

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

Example 1:

Input: nums = [3,4,9,1,3,9,5], key = 9, k = 1
Output: [1,2,3,4,5,6]
Explanation: 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]
Explanation: 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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values of `key` and `k`? Could `key` be negative, zero, or very large?
What should I return if no indices meet the k-distance criteria? Should I return an empty list?
Can the input array `nums` contain duplicate elements, and if so, should the same index be added to the result multiple times if it's k-distant from multiple occurrences of `key`?
Are there any constraints on the size of the input array `nums`? For example, is it possible that `nums` is empty?
Is the returned list of indices expected to be sorted in ascending order?

Brute Force Solution

Approach

The brute force method means we check everything. For this problem, we will look at each spot in the list of numbers and see if it's near a 'special' number. If it is, we remember that spot.

Here's how the algorithm would work step-by-step:

Go through each number in the list, one at a time.
For the current number, check every other number in the list to see if it's a 'special' number.
If you find a 'special' number that's close enough (within a certain distance), then remember the current number's spot in the list.
After checking all other numbers to see if they are 'special' numbers close enough to the current number, move on to the next number in the original list.
Repeat this process until you've checked every single number in the original list.
At the end, you'll have a collection of spots from the original list that were near a 'special' number. These are your answer.

Code Implementation

def find_all_k_distant_indices(numbers, key, distance):
    k_distant_indices = []

    for current_index in range(len(numbers)):
        for special_index in range(len(numbers)):
            # Check if the current element is a key
            if numbers[special_index] == key:

                # Check if the special index is within the specified distance
                if abs(current_index - special_index) <= distance:

                    # Add the current index to the result if it's not already there.
                    if current_index not in k_distant_indices:
                        k_distant_indices.append(current_index)

    k_distant_indices.sort()
    return k_distant_indices

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the input array nums. For each element, it iterates through all n elements of the array indices to check if the element at that index is within a distance k of the current element. This results in a nested loop structure where the outer loop runs n times and the inner loop also runs n times, performing a constant amount of work within the inner loop. Therefore, the total number of operations is proportional to n * n, simplifying to O(n²).

Space Complexity

O(N) – The algorithm iterates through each number in the list and potentially adds its index to a collection of 'special' indices. This collection of 'special' indices represents the auxiliary space. In the worst-case scenario, every index could be considered 'special', requiring a list or array to store all N indices, where N is the size of the input list. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The key is to avoid redundant checks. Instead of independently evaluating each position in the list, we progressively build our answer by only considering the important places and their surroundings.

Here's how the algorithm would work step-by-step:

First, identify all the important positions in the list. These are the positions that have the value we're looking for.
Next, go through the entire list, position by position. For each position, check if it's close enough to any of the important positions we found earlier.
To determine if a position is 'close enough', see if its distance to any important position is within the specified limit.
If it is close enough to an important position, then add that position to our answer.
Finally, after checking every position in the list, the answer contains all the positions that meet the criteria.

Code Implementation

def find_k_distant_indices(numbers, key, distance):
    important_indices = []
    for index, number in enumerate(numbers):
        if number == key:
            important_indices.append(index)

    result = []
    for i in range(len(numbers)):
        # Check if the current index is within distance of any important index.
        for important_index in important_indices:
            if abs(i - important_index) <= distance:
                result.append(i)

                #Avoid duplicates by breaking after first match.
                break

    #Removing duplicates while preserving order.
    final_result = []
    for index in result:
        if index not in final_result:
            final_result.append(index)

    return final_result

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm first identifies all indices i where nums[i] == key, which takes O(n) time where n is the length of the nums array. Let m be the number of such indices. Then, for each index j in the entire array (0 to n-1), the algorithm iterates through these m key indices to check if abs(i-j) <= k. Therefore, in the worst case, for each of the n indices, we iterate through all m key indices. Thus, the overall time complexity is O(n*m).

Space Complexity

O(N) – The algorithm identifies 'important positions' and, based on the plain English explanation, it implies storing them. In the worst-case scenario, every index could be an 'important position'. This would require an auxiliary list (or similar data structure) to store these positions. Therefore, the extra space needed grows linearly with the size of the input array, N. The final answer list will also grow up to N size in the worst case.

Edge Cases

Case	How to Handle
Null input array	Return an empty list or throw an IllegalArgumentException.
Empty input array	Return an empty list as there are no indices to check.
k is negative	Treat k as its absolute value or throw an IllegalArgumentException, since distance cannot be negative.
k is zero	The condition `abs(i - j) <= k` becomes `i == j`, so only indices equal to their original value should be added to the list.
Array with all identical values	The algorithm should correctly identify all indices within the distance k of any index.
Large array size and large k value	Ensure the solution's time complexity is efficient, potentially avoiding nested loops for optimal performance.
Integer overflow when calculating absolute difference of indices	Use appropriate data types (e.g., long) to prevent overflow during index subtraction when `i` or `j` are close to Integer.MAX_VALUE or Integer.MIN_VALUE.
No indices satisfy the condition	The algorithm should return an empty list when no indices meet the k-distant requirement.

Null input array

How to Handle:

Return an empty list or throw an IllegalArgumentException.

Empty input array

How to Handle:

Return an empty list as there are no indices to check.

k is negative

How to Handle:

Treat k as its absolute value or throw an IllegalArgumentException, since distance cannot be negative.

k is zero

How to Handle:

The condition `abs(i - j) <= k` becomes `i == j`, so only indices equal to their original value should be added to the list.

Array with all identical values

How to Handle:

The algorithm should correctly identify all indices within the distance k of any index.

Large array size and large k value

How to Handle:

Ensure the solution's time complexity is efficient, potentially avoiding nested loops for optimal performance.

Integer overflow when calculating absolute difference of indices

How to Handle:

Use appropriate data types (e.g., long) to prevent overflow during index subtraction when `i` or `j` are close to Integer.MAX_VALUE or Integer.MIN_VALUE.

No indices satisfy the condition

How to Handle:

The algorithm should return an empty list when no indices meet the k-distant requirement.