2200. Find All K-Distant Indices in an Array LeetCode Solution
In this guide, you will get 2200. Find All K-Distant Indices in an Array LeetCode Solution with the best time and space complexity. The solution to Find All K-Distant Indices in an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find All K-Distant Indices in an Array
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.
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(|\texttt{ans}|)
2200. Find All K-Distant Indices in an Array LeetCode Solution in C++
class Solution {
public:
vector<int> findKDistantIndices(vector<int>& nums, int key, int k) {
const int n = nums.size();
vector<int> ans;
for (int i = 0, j = 0; i < n; ++i) {
// the first index j s.t. nums[j] == key and j >= i - k
while (j < n && (nums[j] != key || j < i - k))
++j;
if (j == n)
break;
if (abs(i - j) <= k)
ans.push_back(i);
}
return ans;
}
}; /* code provided by PROGIEZ */
2200. Find All K-Distant Indices in an Array LeetCode Solution in Java
class Solution {
public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
final int n = nums.length;
List<Integer> ans = new ArrayList<>();
for (int i = 0, j = 0; i < n; ++i) {
// the first index j s.t. nums[j] == key and j >= i - k
while (j < n && (nums[j] != key || j < i - k))
++j;
if (j == n)
break;
if (Math.abs(i - j) <= k)
ans.add(i);
}
return ans;
}
} // code provided by PROGIEZ
2200. Find All K-Distant Indices in an Array LeetCode Solution in Python
class Solution:
def findKDistantIndices(self, nums: list[int], key: int, k: int) -> list[int]:
n = len(nums)
ans = []
j = 0
for i in range(n):
# the first index j s.t. nums[j] == key and j >= i - k
while j < n and (nums[j] != key or j < i - k):
j += 1
if j == n:
break
if abs(i - j) <= k:
ans.append(i)
return ans # code by PROGIEZ
