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 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.

Clarifying Questions

Before diving into the solution, it’s good to ask a few clarifying questions:

1. What is the range of values for nums, key, and k?
   • Usually, the constraints are provided to limit the size for computation feasibility.
2. Can nums contain negative numbers or zeros?
   • Depending on the context, nums could include negative numbers or zeros. It’s essential to know for precise implementation.
3. Are there any specific requirements on the size of the output list?
   • This helps to understand if pagination or partial results are necessary.
4. Should the indices be returned in sorted order even if they are already naturally sorted?
   • This confirms how strictly we need to follow the described behavior.

Strategy

To solve this problem:

1. Identify all indices j such that nums[j] == key.
2. For each such index j, mark indices i such that |i - j| <= k.
3. Use a data structure, like a set, to keep track of all unique indices and finally convert it to a sorted list.

Code

Here’s one way to implement the solution in Java:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
        Set<Integer> resultSet = new HashSet<>();
        
        // Step 1: Identify all indices with nums[j] == key.
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == key) {
                // Step 2: Add all indices i such that |i - j| <= k.
                for (int i = Math.max(0, j - k); i <= Math.min(nums.length - 1, j + k); i++) {
                    resultSet.add(i);
                }
            }
        }
        
        // Step 3: Convert the set to a list and sort it.
        List<Integer> result = new ArrayList<>(resultSet);
        result.sort(Integer::compareTo); // Ensure the list is sorted in increasing order.
        
        return result;
    }

    // The driver code can be added here for testing the function.
}

Time Complexity

• Identifying all indices for the key: This takes O(n) time where n is the length of nums.
• Marking k-distant indices: In the worst case, this involves making k additions for each key index. This results in O(m * k) operations, where m is the number of key indices.
• Sorting the resulting set: Converting a set to a list and sorting it would take O(p log p) where p is the number of unique indices.

Overall, the time complexity is O(n + (m * k) + p log p), which simplifies to O(n * k) in the worst case, assuming that sorting dominates the other operations for large inputs.

In a typical scenario where k is much smaller than n, this approach is efficient and straightforward.

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?