Is Find Occurrences of an Element in an Array easy or hard?

The problem is rated Medium because the brute-force solution is simple but inefficient for many queries. Recognizing the need for preprocessing with a hash map and storing indices is the key insight that leads to the optimal solution.

Find Occurrences of an Element in an Array Python/Java solution

In Python, use a dictionary mapping values to lists of indices and return list[k-1] if it exists. In Java, use a HashMap > to store occurrence indices and answer queries in constant time.

How to solve Find Occurrences of an Element in an Array in O(n)?

Build a hash map that stores the indices of every occurrence of each value during a single pass through the array. After preprocessing, answering a query for the k-th occurrence simply checks the stored list and returns the element at index k-1 if it exists.

What is the best approach for Find Occurrences of an Element in an Array?

The most efficient approach is preprocessing with index mapping. Traverse the array once and store all indices of each value in a hash map. Each query then retrieves the k-th occurrence directly from the stored list in O(1) time, resulting in O(n + q) total complexity.

Is Find Occurrences of an Element in an Array asked at Google/Amazon/Meta?

Problems involving occurrence indexing and preprocessing arrays appear frequently in interviews at large tech companies. Variations of this pattern show up at companies like Amazon and Google where candidates must optimize repeated queries over static data.

What data structure is used in Find Occurrences of an Element in an Array?

The optimized solution uses a hash table (dictionary) that maps each value to a list of indices where it appears. This structure allows constant-time lookup of the k-th occurrence after preprocessing.

What is the time complexity of Find Occurrences of an Element in an Array?

The naive solution takes O(n * q) time because the array is scanned for every query. The optimized approach preprocesses the array in O(n) and answers each query in O(1), giving an overall time complexity of O(n + q).

3159. Find Occurrences of an Element in an Array - Practice Online

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 1^st query, the first occurrence of 1 is at index 0.
For the 2^nd query, there are only two occurrences of 1 in nums, so the answer is -1.
For the 3^rd query, the second occurrence of 1 is at index 2.
For the 4^th 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 1^st query, 5 doesn't exist in nums, so the answer is -1.

Constraints:

1 <= nums.length, queries.length <= 10⁵
1 <= queries[i] <= 10⁵
1 <= nums[i], x <= 10⁴