algoadvance

Leetcode 2200. Find All K

Problem Statement

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 an index j such that |i - j| ≤ k and nums[j] == key.

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

Example:

Input: nums = [3,4,9,1,3,9,5], key = 9, k = 1
Output: [1,2,3,4,5,6]
Explanation: Here, nums[3] and nums[5] are the indices with value 9, and they affect the adjacent indices within a range of 1. Therefore, the resulting indices are [1, 2, 3, 4, 5, 6].

Clarifying Questions

1. Input Constraints:
   • What is the length of the array nums?
   • Are there constraints on the values within the array nums or the values of key and k?
2. Output Requirements:
   • Should the output indices be returned in a sorted order? (Assuming yes as mentioned in the problem statement)
3. Edge Cases:
   • How should the function handle the cases where no elements in nums match key?
   • How should the function handle cases where k is much larger than the length of nums?

Strategy

1. Identify Key Indices:
   • Traverse the array nums to find all indices j where nums[j] == key.
2. Mark K-Distant Indices:
   • Create an empty set or list to store the k-distant indices.
   • For each key index j, compute the range of indices influenced by this key index as [max(0, j - k), min(len(nums) - 1, j + k)].
3. Store Unique Indices:
   • As we find the k-distant indices for each key index, store them in a set to avoid duplicates and ensure uniqueness.
4. Sort and Return:
   • Convert the set of indices into a sorted list and return it.

Code

Here’s the C++ code that implements the strategy:

#include <vector>
#include <set>
#include <algorithm>

std::vector<int> findKDistantIndices(std::vector<int>& nums, int key, int k) {
    std::set<int> kDistantIndices;

    // Find all indices containing the key
    for (int j = 0; j < nums.size(); ++j) {
        if (nums[j] == key) {
            // Add k-distant indices for each key occurrence
            for (int i = std::max(0, j - k); i <= std::min(int(nums.size()) - 1, j + k); ++i) {
                kDistantIndices.insert(i);
            }
        }
    }

    // Convert set to sorted vector
    return std::vector<int>(kDistantIndices.begin(), kDistantIndices.end());
}

Time Complexity

• Finding Key Indices: O(n) where n is the length of nums (single traversal to find key indices).
• Marking K-Distant Indices: For each key index, marking K-Distant indices can take O(k). In the worst case, if every element is a key, it will take O(n * k), but each element within this range would be marked only once.
• Overall Complexity: The complexity is dominated by O(n * k) in the worst case.

Space Complexity

• Auxiliary space for storing indices: O(n) where n is the size of the set (in the worst case, the set may store each element of the array).
• Result vector: Also O(n), since it could potentially include every index.

Overall, the algorithm is efficient given the constraints typically present in such problems.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?