# Find Occurrences of an Element in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-occurrences-of-an-element-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/find-occurrences-of-an-element-in-an-array
**Data structures:** Array, Hash Table
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
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`

# Approaches
## Brute Force: Iterating for Each Query
This is a straightforward, brute-force solution. For each query, we perform a full scan of the `nums` array from the beginning. We keep a count of the occurrences of `x` we've seen so far. When the count matches the desired occurrence number from the query, we record the current index and move to the next query. If we scan the entire array and don't find the required number of occurrences, the answer for that query is -1.
**Time:** O(N * Q), where N is the length of `nums` and Q is the length of `queries`. In the worst-case scenario, for each of the Q queries, we may need to traverse the entire `nums` array. · **Space:** O(Q) to store the answer array. Excluding the output array, the space complexity is O(1) as we only use a few variables to process each query.
**Pros:** Simple to understand and implement.; Uses O(1) extra space (if the output array is not considered).
**Cons:** Extremely inefficient for large inputs due to its nested loop structure.; The time complexity is quadratic, O(N * Q), which will lead to a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode given the problem constraints.
### Explanation
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.

```java
class Solution {
    public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {
        int[] answer = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int k = queries[i];
            int count = 0;
            int foundIndex = -1;

            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == x) {
                    count++;
                    if (count == k) {
                        foundIndex = j;
                        break; // Found the k-th occurrence, no need to search further for this query
                    }
                }
            }
            answer[i] = foundIndex;
        }

        return answer;
    }
}
```
### Algorithm
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.

## Optimized Approach: Pre-computation of Indices
This optimized approach avoids the redundant work of the brute-force method. Instead of scanning the `nums` array for every query, we can pre-process it. We do a single pass through `nums` to find and store the indices of all occurrences of `x`. Once we have this list of indices, answering each query becomes a simple and fast lookup operation.
**Time:** O(N + Q), where N is the length of `nums` and Q is the length of `queries`. The algorithm consists of one pass over `nums` (O(N)) and one pass over `queries` (O(Q)). This is the optimal time complexity. · **Space:** O(K + Q), where K is the number of occurrences of `x` in `nums` (K <= N) and Q is the length of `queries`. The space is used for the `xIndices` list and the `answer` array. In the worst case, this is O(N + Q).
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Answers each query in constant time after the initial pre-computation.
**Cons:** Requires extra space to store the indices of `x`. In the worst case, if all elements in `nums` are `x`, this space can be O(N).
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {
        // Step 1 & 2: Pre-compute and store indices of x
        List<Integer> xIndices = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == x) {
                xIndices.add(i);
            }
        }

        // Step 3 & 4: Process queries using the pre-computed list
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int k = queries[i];
            
            // Step 5, 6, 7: Check validity and retrieve the index
            // k is 1-based, list indices are 0-based
            if (k > 0 && k <= xIndices.size()) {
                answer[i] = xIndices.get(k - 1);
            } else {
                answer[i] = -1;
            }
        }

        return answer;
    }
}
```
### Algorithm
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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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]

```