Find Occurrences of an Element in an Array

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

Key Insights

• The problem involves counting occurrences of a specific integer in an array and responding to multiple queries based on those counts.
• Efficiently retrieving the index of occurrences requires preprocessing the nums array to store the indices of x.
• Each query is independent and can be answered in constant time after preprocessing.

Space and Time Complexity

Time Complexity: O(n + q), where n is the length of nums and q is the length of queries. This accounts for the initial pass through nums to collect indices and then a pass through queries to generate results.

Space Complexity: O(k), where k is the number of occurrences of x in nums, as we store these indices in a list.

Solution

The solution involves the following steps:

1. Traverse the nums array to collect indices of all occurrences of x in a list.
2. For each query, check if it is less than or equal to the number of occurrences collected. If so, return the corresponding index; otherwise, return -1.

Code Solutions