# 3159. Find Occurrences of an Element in an Array

## Description

You are given an integer array nums, an integer array queries, and an integer x.

For each queries[i], you need to find the index of the queries[i]th occurrence of x in the nums array. If there are fewer than queries[i] occurrences of x, the answer should be -1 for that query.

Return an integer array answer containing the answers to all queries.

Example 1:

Input: nums = [1,3,1,7], queries = [1,3,2,4], x = 1

Output: [0,-1,2,-1]

Explanation:

• For the 1st query, the first occurrence of 1 is at index 0.
• For the 2nd query, there are only two occurrences of 1 in nums, so the answer is -1.
• For the 3rd query, the second occurrence of 1 is at index 2.
• For the 4th query, there are only two occurrences of 1 in nums, so the answer is -1.

Example 2:

Input: nums = [1,2,3], queries = [10], x = 5

Output: [-1]

Explanation:

• For the 1st query, 5 doesn't exist in nums, so the answer is -1.

Constraints:

• 1 <= nums.length, queries.length <= 105
• 1 <= queries[i] <= 105
• 1 <= nums[i], x <= 104

## Solutions

### Solution 1: Simulation

According to the problem description, we can first traverse the array nums to find the indices of all elements with a value of $x$, and record them in the array ids.

Next, we traverse the array queries. For each query $i$, if $i - 1$ is less than the length of ids, then the answer is ids[i - 1], otherwise, the answer is $-1$.

The time complexity is $O(n + m)$, and the space complexity is $O(n + m)$. Where $n$ and $m$ are the lengths of the arrays nums and queries respectively.

• class Solution {
public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {
List<Integer> ids = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
if (nums[i] == x) {
ids.add(i);
}
}
int m = queries.length;
int[] ans = new int[m];
for (int i = 0; i < m; ++i) {
int j = queries[i] - 1;
ans[i] = j < ids.size() ? ids.get(j) : -1;
}
return ans;
}
}

• class Solution {
public:
vector<int> occurrencesOfElement(vector<int>& nums, vector<int>& queries, int x) {
vector<int> ids;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] == x) {
ids.push_back(i);
}
}
vector<int> ans;
for (int& i : queries) {
ans.push_back(i - 1 < ids.size() ? ids[i - 1] : -1);
}
return ans;
}
};

• class Solution:
def occurrencesOfElement(
self, nums: List[int], queries: List[int], x: int
) -> List[int]:
ids = [i for i, v in enumerate(nums) if v == x]
return [ids[i - 1] if i - 1 < len(ids) else -1 for i in queries]


• func occurrencesOfElement(nums []int, queries []int, x int) (ans []int) {
ids := []int{}
for i, v := range nums {
if v == x {
ids = append(ids, i)
}
}
for _, i := range queries {
if i-1 < len(ids) {
ans = append(ans, ids[i-1])
} else {
ans = append(ans, -1)
}
}
return
}

• function occurrencesOfElement(nums: number[], queries: number[], x: number): number[] {
const ids: number[] = nums.map((v, i) => (v === x ? i : -1)).filter(v => v !== -1);
return queries.map(i => ids[i - 1] ?? -1);
}