2200. Find All K-Distant Indices in an Array

Problem Description

You're provided with an array nums and two integers key and k. The task is to find all indices in the array that are within a distance of k from any occurrence of key in the array. An index i is considered k-distant if there is at least one occurrence of key at index j such that the absolute difference between i and j is less than or equal to k. The challenge is to return all such k-distant indices in ascending order.

The problem focuses on finding these indices efficiently and ensuring that the distance condition (|i - j| <= k) is met for each index related to the key value. In essence, you're creating a list of indices where each index is not too far from any position in the array that contains the key you're interested in.

Intuition

To solve this problem, one straightforward approach is to check each index and compare it with every other index to determine if it meets the k-distance condition with respect to the key.

Here are the steps involved in this approach:

Loop through each index i of the array.
For each index i, loop through the entire array again and check every index j.
As soon as you find an index j where nums[j] equals key and |i - j| <= k, you know that i is a valid k-distant index.
Add the index i to the answer list (ans) as soon as the condition is satisfied and stop the inner loop to avoid duplicates.
Once the loops complete, you will have a list of all k-distant indices.
Since we begin the search from the start of the array and never revisit indices we've already determined to be k-distant, the resulting list is naturally sorted in increasing order.

The intuition behind this method relies on a brute-force strategy, checking every possible pair to ensure no potential k-distant index is missed. The break statement after adding an index to ans ensures we're not adding the same index multiple times.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's fasterIt has better space complexityOrder of computer subproblems does not matterIt has better time complexity

I don’t know

Solution Approach

The Reference Solution Approach provided above implements a brute-force method to identify all k-distant indices. The algorithm does not use any complex data structures or patterns but a simple approach to comparing indices with straightforward nested for-loops. Here's an explanation of how the implementation works:

We start by initializing an empty list ans that will store our final list of k-distant indices.
We determine the length of the nums array and store it in variable n, which is used to control the loop boundaries.
A for-loop runs with i ranging from 0 to n - 1, iterating over each index in the array. For each iteration (for each index i), we want to check if it is a k-distant index.
Inside the outer loop, another for-loop runs with j ranging from 0 to n - 1. This inner loop scans the entire array to check for occurrences of key.
For every index j, if nums[j] equals key and the absolute difference between i and j (abs(i - j)) is less than or equal to k, we've found that index i is k-distant from an occurrence of key.
As soon as the condition is met (nums[j] == key and abs(i - j) <= k), we append the current index i to the ans list, ensuring that each index is only added once due to the break statement that follows the append operation. The break ensures the algorithm moves to the next index i once it confirms that i is k-distant.
After both loops have completed their execution, the list ans contains all of the k-distant indices. The outer loop's sequential nature guarantees that ans is sorted in increasing order, as indices are checked starting from the smallest i to the largest.

This solution has a time complexity of O(n^2) due to the nested for-loops each ranging from 0 to n-1. There is no additional space complexity aside from the output array ans, and thus the space complexity is O(n) in the worst case, where n is the number of k-distant indices found.

While this brute-force method guarantees a correct solution by exhaustively checking all conditions, it may not be the most efficient for larger arrays due to its quadratic time complexity. Optimizations can be considered using different algorithms or data structures if efficiency is critical.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayQuick sort does not use divide and conquer

I don’t know

Example Walkthrough

To illustrate the solution approach, let's consider an example. Suppose we have the array nums = [1, 2, 3, 2, 4], with key = 2 and k = 2.

We are tasked with finding all indices in the array that are at most 2 steps away from any occurrence of the number 2. Following the steps of the solution approach:

We start with an empty list ans.
The length of nums is 5 (n = 5).
We start an outer loop with i ranging from 0 to 4 (since n - 1 = 4).
Now, for each i, we will check every other index j for an occurrence of key that is k-distant.

Let's see how this unfolds step by step:

For i = 0, we check every j. We find that j = 1 satisfies nums[j] == key and abs(i - j) <= k (1 - 0 <= 2), so we add i = 0 to ans and break the inner loop.
For i = 1, key is present at this same index j = 1 and abs(i - j) = 0 which is within k distance, so we add i = 1 to ans and break the inner loop.
For i = 2, the next occurrence of key is at j = 1. The condition nums[1] == key and abs(2 - 1) <= k is true, so add i = 2 to ans and break the inner loop.
For i = 3, we find that j = 3 satisfies nums[j] == key as well, and abs(i - j) = 0 is within k distance, so we add i = 3 to ans and break the inner loop.
For i = 4, the closest key is at j = 3, but abs(4 - 3) <= k is true, so we also add i = 4 to ans and break the inner loop.

After the loops complete, our ans list contains [0, 1, 2, 3, 4]. Each index is within a distance of k from an occurrence of the key. Thus, we have successfully found all k-distant indices using the brute-force approach.

Solution Implementation

1class Solution:
2    def find_k_distant_indices(self, nums: List[int], key: int, k: int) -> List[int]:
3        # Initialize an empty list to store the answer
4        result_indices = []
5        # Get the length of the input list 'nums'
6        num_count = len(nums)
7        # Loop over each element in 'nums'
8        for i in range(num_count):
9            # Loop over the elements in 'nums' again for each 'i'
10            for j in range(num_count):
11                # Check if the current element is the 'key' and its index 'j' is within 'k' distance from 'i'
12                if abs(i - j) <= k and nums[j] == key:
13                    # If the condition is met, add the index 'i' to 'result_indices'
14                    result_indices.append(i)
15                    # Stop checking other 'j's for the current 'i' as we've found a qualifying 'j'
16                    break
17        # Return the list of indices satisfying the condition
18        return result_indices
19

1class Solution {
2    public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
3        // The length of the array 'nums'
4        int n = nums.length;
5        // Initialize the list to store the answer
6        List<Integer> kDistantIndices = new ArrayList<>();
7        // Iterate over all elements of 'nums'
8        for (int i = 0; i < n; ++i) {
9            // Check elements again to find indices within distance 'k' of 'key' in 'nums'
10            for (int j = 0; j < n; ++j) {
11                // If the absolute difference between indices 'i' and 'j' is less than or equal to 'k'
12                // and the current element nums[j] is equal to 'key', the condition is met
13                if (Math.abs(i - j) <= k && nums[j] == key) {
14                    // Add the current index 'i' to the list of results
15                    kDistantIndices.add(i);
16                    // Break from the inner loop since we've found the key at this 'i' index
17                    break;
18                }
19            }
20        }
21        // Return the list of indices that are within distance 'k' from the elements equal to 'key'
22        return kDistantIndices;
23    }
24}
25

1#include <vector>
2#include <cstdlib> // Include for std::abs
3
4class Solution {
5public:
6    // Function to find all indices within 'k' distance from elements equal to 'key'
7    vector<int> findKDistantIndices(vector<int>& nums, int key, int k) {
8        int n = nums.size(); // Get the size of the input vector
9        vector<int> resultIndices; // Vector to store result indices
10      
11        // Iterate over all elements in 'nums'
12        for (int i = 0; i < n; ++i) {
13          
14            // Check the distance of current 'i' to all elements in 'nums'
15            for (int j = 0; j < n; ++j) {
16              
17                // If the absolute difference between indices 'i' and 'j' is less than or equal to 'k'
18                // and the element at 'j' is equal to 'key'
19                if (std::abs(i - j) <= k && nums[j] == key) {
20                    resultIndices.push_back(i); // Add 'i' to the result indices
21                    break; // Stop inner loop since 'i' is within the distance 'k' from an element equal to 'key'
22                }
23            }
24        }
25      
26        return resultIndices; // Return the vector with the result indices
27    }
28};
29

1function findKDistantIndices(nums: number[], key: number, k: number): number[] {
2    const numsLength = nums.length; // Holds the length of the nums array
3    let distantIndices = []; // Array to store the result
4
5    // Iterate over each element in nums array
6    for (let index = 0; index < numsLength; index++) {
7        // Check if the current element is equal to the key
8        if (nums[index] === key) {
9            // For each element matching the key, compute the range of indices within k distance
10            for (let i = index - k; i <= index + k; i++) {
11                // Ensure the computed index is within array bounds and not already included in the result
12                if (i >= 0 && i < numsLength && !distantIndices.includes(i)) {
13                    distantIndices.push(i); // Add the index to the result
14                }
15            }
16        }
17    }
18
19    return distantIndices; // Return the array of k-distant indices
20}
21

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The given code consists of two nested loops, each iterating over the array nums which has n elements.

The outer loop runs n times for every element i in the array nums.
For each iteration of i, the inner loop also checks every element j over the entire array.

When checking the condition if abs(i - j) <= k and nums[j] == key:, it performs constant time checks which can be considered as O(1).

Hence, the time complexity of the code is O(n^2) since for each element of nums, the code iterates over the entire nums again.

Space Complexity

The space complexity of the algorithm comes from the list ans which stores the indices. In the worst case, where the condition abs(i - j) <= k and nums[j] == key is true for every element, ans could have the same length as the number of elements in nums. This means that it could potentially store n indices. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2200. Find All K-Distant Indices in an Array

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings