Watch 10 video solutions for Find Occurrences of an Element in an Array, a medium level problem involving Array, Hash Table. This walkthrough by Road To FAANG has 531 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
nums, so the answer is -1.nums, so the answer is -1.Example 2:
Input: nums = [1,2,3], queries = [10], x = 5
Output: [-1]
Explanation:
nums, so the answer is -1.
Constraints:
1 <= nums.length, queries.length <= 1051 <= queries[i] <= 1051 <= nums[i], x <= 104Problem Overview: You are given an integer array and queries asking for the index of the k-th occurrence of a specific value x. If the array does not contain enough occurrences, return -1. The core challenge is answering occurrence queries efficiently.
Approach 1: Naive Linear Search (O(n * q) time, O(1) space)
The straightforward approach scans the array for every query. For each query k, iterate through the array and count how many times x appears. When the counter reaches k, return the current index. If the scan finishes before reaching k, the answer is -1. This solution uses only constant extra space but performs a full array traversal for each query. When the number of queries grows large, repeated scans make the total runtime O(n * q). It works fine for small inputs and helps verify correctness before optimizing.
Approach 2: Preprocessing with Index Mapping (O(n + q) time, O(n) space)
A more efficient strategy preprocesses the array once. Iterate through the array and record the indices where each value appears. A hash table or dictionary maps each value to a list of its occurrence indices. For example, if x appears at indices [1, 4, 7], the 1st, 2nd, and 3rd occurrences correspond directly to those positions. After preprocessing, each query becomes a constant-time lookup: check if the list for x has at least k elements and return list[k-1]; otherwise return -1. The preprocessing pass over the array costs O(n), and each query is O(1), making the total runtime O(n + q).
This approach trades memory for speed. Storing all occurrence indices requires up to O(n) extra space, but it eliminates repeated scans. When queries are frequent, the improvement is substantial because the expensive work is done only once during preprocessing.
Recommended for interviews: Start by explaining the linear scan. It shows you understand the requirement and how to count occurrences directly. Then move to the index mapping optimization using a hash map. Interviewers typically expect the preprocessing approach because it reduces repeated work and achieves O(n + q) time. The pattern of storing indices for fast query lookups appears often in array preprocessing and hash table-based problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Linear Search | O(n * q) | O(1) | When queries are few or input size is small |
| Preprocessing with Index Mapping | O(n + q) | O(n) | Best general solution when many queries must be answered quickly |