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.
This approach involves iterating through the nums array for each query. For each query, we count occurrences of the target value x until the required occurrence is found or the list ends. This method answers each query in linear time in the worst-case scenario.
The function findOccurrences iterates over queries, and for each query, it iterates over nums to count occurrences of x. When the desired occurrence is found, it stores the index. Otherwise, it records -1 if the desired occurrence isn't reached.
Time Complexity: O(q * n) where q is the size of queries and n is the size of nums.
Space Complexity: O(1).
This approach leverages preprocessing by first scanning the nums array to store indices of all occurrences of x. This allows each query to be resolved in constant time, significantly improving efficiency when multiple queries are processed.
This C implementation utilizes an indexMap to store indices of any occurrences of x in nums. Each query is resolved in constant time by checking if the query index is within bounds of indexMap and referencing the appropriate index.
Time Complexity: O(n + q).
Space Complexity: O(n) for the index map.
| Approach | Complexity |
|---|---|
| Naive Linear Search | Time Complexity: O(q * n) where q is the size of queries and n is the size of nums. |
| Preprocessing with Index Mapping | Time Complexity: O(n + q). |
| 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 |
Leetcode 3159 | Find Occurrences of an Element in an Array | Leetcode Biweekly Contest 131 • Road To FAANG • 531 views views
Watch 9 more video solutions →Practice Find Occurrences of an Element in an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor