Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2200.html
2200. Find All K-Distant Indices in an Array (Easy)
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] == keyandnums[5] == key. - For index 0, |0 - 2| > k and |0 - 5| > k, so there is no jwhere|0 - j| <= kandnums[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 <= 10001 <= nums[i] <= 1000keyis an integer from the arraynums.1 <= k <= nums.length
Similar Questions:
Solution 1. Two Pointers
-
// OJ: https://leetcode.com/problems/find-all-k-distant-indices-in-an-array/ // Time: O(N) // Space: O(N) class Solution { public: vector<int> findKDistantIndices(vector<int>& A, int key, int k) { int N = A.size(); vector<int> ans, idx; for (int i = 0; i < N; ++i){ if (A[i] == key) idx.push_back(i); // `idx` is a list of indices whose corresponding value is `key`. } for (int i = 0, j = 0; i < N && j < idx.size(); ++i) { if (i < idx[j] - k) continue; // If `i` is not yet in range of the next `key` element at `idx[j]`, skip. while (j < idx.size() && i > idx[j] + k) ++j; // While `i > idx[j] + k`, keep incrementing `j` to bring `idx[j]` in range of `i`. if (j < idx.size() && i <= idx[j] + k && i >= idx[j] - k) ans.push_back(i); // add `i` to the answer if `idx[j] - k <= i <= idx[j] + k`. } return ans; } }; -
class Solution: def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]: ans = [] n = len(nums) for i in range(n): for j in range(n): if abs(i - j) <= k and nums[j] == key: ans.append(i) break return ans ############ # 2200. Find All K-Distant Indices in an Array # https://leetcode.com/problems/find-all-k-distant-indices-in-an-array/ class Solution: def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]: n = len(nums) indices = [i for i, x in enumerate(nums) if x == key] res = [] for i in range(n): for j in indices: if abs(i - j) <= k: res.append(i) break return res -
class Solution { public List<Integer> findKDistantIndices(int[] nums, int key, int k) { int n = nums.length; List<Integer> ans = new ArrayList<>(); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (Math.abs(i - j) <= k && nums[j] == key) { ans.add(i); break; } } } return ans; } } -
func findKDistantIndices(nums []int, key int, k int) []int { n := len(nums) var ans []int for i := 0; i < n; i++ { for j, v := range nums { if abs(i-j) <= k && v == key { ans = append(ans, i) break } } } return ans } func abs(x int) int { if x < 0 { return -x } return x } -
function findKDistantIndices(nums: number[], key: number, k: number): number[] { const n = nums.length; let ans = []; for (let j = 0; j < n; j++) { if (nums[j] == key) { for (let i = j - k; i <= j + k; i++) { if (i >= 0 && i < n && !ans.includes(i)) { ans.push(i); } } } } return ans; }
Solution 2. Two Pointers
-
// OJ: https://leetcode.com/problems/find-all-k-distant-indices-in-an-array/ // Time: O(N) // Space: O(1) class Solution { public: vector<int> findKDistantIndices(vector<int>& A, int key, int k) { int N = A.size(), j = 0; vector<int> ans; for (int i = 0, j = 0; i < N; ++i) { while (j < N && (A[j] != key || j < i - k)) ++j; // Find the first index `j` that `A[j] == key` and `j >= i - k`. if (j == N) break; if (i <= j + k && i >= j - k) ans.push_back(i); // add `i` to answer if `j - k <= i <= j + k`. } return ans; } }; -
class Solution: def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]: ans = [] n = len(nums) for i in range(n): for j in range(n): if abs(i - j) <= k and nums[j] == key: ans.append(i) break return ans ############ # 2200. Find All K-Distant Indices in an Array # https://leetcode.com/problems/find-all-k-distant-indices-in-an-array/ class Solution: def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]: n = len(nums) indices = [i for i, x in enumerate(nums) if x == key] res = [] for i in range(n): for j in indices: if abs(i - j) <= k: res.append(i) break return res -
class Solution { public List<Integer> findKDistantIndices(int[] nums, int key, int k) { int n = nums.length; List<Integer> ans = new ArrayList<>(); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (Math.abs(i - j) <= k && nums[j] == key) { ans.add(i); break; } } } return ans; } } -
func findKDistantIndices(nums []int, key int, k int) []int { n := len(nums) var ans []int for i := 0; i < n; i++ { for j, v := range nums { if abs(i-j) <= k && v == key { ans = append(ans, i) break } } } return ans } func abs(x int) int { if x < 0 { return -x } return x } -
function findKDistantIndices(nums: number[], key: number, k: number): number[] { const n = nums.length; let ans = []; for (let j = 0; j < n; j++) { if (nums[j] == key) { for (let i = j - k; i <= j + k; i++) { if (i >= 0 && i < n && !ans.includes(i)) { ans.push(i); } } } } return ans; }
Discuss
https://leetcode.com/problems/find-all-k-distant-indices-in-an-array/discuss/1845499