Find Occurrences of an Element in an Array

1. Initialize an integer array answer with the same length as queries.
2. Iterate through each query k at index i in the queries array.
3. For each k, initialize a counter count to 0 and a variable foundIndex to -1.
4. Iterate through the nums array from left to right with index j.
5. If nums[j] is equal to the target value x, increment count.
6. If count becomes equal to k, it means we have found the k-th occurrence. Set foundIndex to the current index j and break the inner loop.
7. After the inner loop finishes, assign foundIndex to answer[i].
8. After iterating through all queries, return the answer array.

The core idea is to process each query independently. For a query asking for the k-th occurrence, we iterate through nums and count how many times we've encountered x. When our count reaches k, the index at that point is our answer. This process is repeated for every single query in the queries array.

1class Solution {2    public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {3        int[] answer = new int[queries.length];4 5        for (int i = 0; i < queries.length; i++) {6            int k = queries[i];7            int count = 0;8            int foundIndex = -1;9 10            for (int j = 0; j < nums.length; j++) {11                if (nums[j] == x) {12                    count++;13                    if (count == k) {14                        foundIndex = j;15                        break; // Found the k-th occurrence, no need to search further for this query16                    }17                }18            }19            answer[i] = foundIndex;20        }21 22        return answer;23    }24}

1. Create a dynamic list, for example, an ArrayList in Java, to store the indices of all occurrences of x. Let's call it xIndices.
2. Iterate through the nums array once from i = 0 to nums.length - 1.
3. If nums[i] is equal to x, add the index i to the xIndices list.
4. Initialize an integer array answer with the same length as queries.
5. Iterate through each query k at index i in the queries array.
6. The k-th occurrence corresponds to the index k-1 in our xIndices list (since lists are 0-indexed).
7. Check if k is a valid occurrence number, i.e., if k > 0 and k <= xIndices.size().
8. If it is valid, the answer is xIndices.get(k - 1). Assign this value to answer[i].
9. If it is not valid, it means there are fewer than k occurrences of x. Assign -1 to answer[i].
10. After processing all queries, return the answer array.

The key insight is to decouple the search for x from the processing of queries. We first build a data structure that maps the occurrence number to its index in the original array. A simple list or dynamic array is perfect for this. The first element in our list is the index of the 1st occurrence, the second element is the index of the 2nd occurrence, and so on.

After this one-time setup which takes O(N) time, each query k can be answered in O(1) time by checking if the k-th element exists in our list (i.e., if k-1 is a valid index) and retrieving it if it does.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {6        // Step 1 & 2: Pre-compute and store indices of x7        List<Integer> xIndices = new ArrayList<>();8        for (int i = 0; i < nums.length; i++) {9            if (nums[i] == x) {10                xIndices.add(i);11            }12        }13 14        // Step 3 & 4: Process queries using the pre-computed list15        int[] answer = new int[queries.length];16        for (int i = 0; i < queries.length; i++) {17            int k = queries[i];18            19            // Step 5, 6, 7: Check validity and retrieve the index20            // k is 1-based, list indices are 0-based21            if (k > 0 && k <= xIndices.size()) {22                answer[i] = xIndices.get(k - 1);23            } else {24                answer[i] = -1;25            }26        }27 28        return answer;29    }30}