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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

1
2
3
4
5
6
7
8


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 <= 10^5
  • 1 <= queries[i] <= 10^5
  • 1 <= nums[i], x <= 10^4

Solution

Method 1 – Index Preprocessing and Direct Lookup

Intuition

The key idea is to first record all indices where x appears in nums. Then, for each query, we can directly check if the required occurrence exists and return its index, or -1 if it doesn’t. This avoids repeated scanning of the array for each query.

Approach

  1. Traverse nums and store the indices where x occurs in a list.
  2. For each value in queries, check if the (query-1)th index exists in the list:
    • If yes, add that index to the answer.
    • If not, add -1.
  3. Return the answer array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    vector<int> occurrencesOfElement(vector<int>& nums, vector<int>& queries, int x) {
        vector<int> idxs, ans;
        for (int i = 0; i < nums.size(); ++i)
            if (nums[i] == x) idxs.push_back(i);
        for (int q : queries)
            ans.push_back(q <= idxs.size() ? idxs[q-1] : -1);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func occurrencesOfElement(nums []int, queries []int, x int) []int {
    idxs := []int{}
    for i, v := range nums {
        if v == x {
            idxs = append(idxs, i)
        }
    }
    ans := make([]int, len(queries))
    for i, q := range queries {
        if q <= len(idxs) {
            ans[i] = idxs[q-1]
        } else {
            ans[i] = -1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public List<Integer> occurrencesOfElement(int[] nums, int[] queries, int x) {
        List<Integer> idxs = new ArrayList<>();
        for (int i = 0; i < nums.length; i++)
            if (nums[i] == x) idxs.add(i);
        List<Integer> ans = new ArrayList<>();
        for (int q : queries)
            ans.add(q <= idxs.size() ? idxs.get(q-1) : -1);
        return ans;
    }
}
1
2
3
4
5
6
7
8

class Solution {
    fun occurrencesOfElement(nums: IntArray, queries: IntArray, x: Int): List<Int> {
        val idxs = mutableListOf<Int>()
        for (i in nums.indices)
            if (nums[i] == x) idxs.add(i)
        return queries.map { if (it <= idxs.size) idxs[it-1] else -1 }
    }
}
1
2
3
4

class Solution:
    def occurrencesOfElement(self, nums: list[int], queries: list[int], x: int) -> list[int]:
        idxs = [i for i, v in enumerate(nums) if v == x]
        return [idxs[q-1] if q <= len(idxs) else -1 for q in queries]
1
2
3
4
5
6

impl Solution {
    pub fn occurrences_of_element(nums: Vec<i32>, queries: Vec<i32>, x: i32) -> Vec<i32> {
        let idxs: Vec<i32> = nums.iter().enumerate().filter_map(|(i, &v)| if v == x { Some(i as i32) } else { None }).collect();
        queries.iter().map(|&q| if (q as usize) <= idxs.len() { idxs[(q-1) as usize] } else { -1 }).collect()
    }
}
1
2
3
4
5
6
7
8

class Solution {
    occurrencesOfElement(nums: number[], queries: number[], x: number): number[] {
        const idxs: number[] = [];
        for (let i = 0; i < nums.length; i++)
            if (nums[i] === x) idxs.push(i);
        return queries.map(q => q <= idxs.length ? idxs[q-1] : -1);
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n is the length of nums and m is the length of queries. We scan nums once and answer each query in constant time.
  • 🧺 Space complexity: O(k + m), where k is the number of occurrences of x (for storing indices), and m for the answer array.