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 <= 104This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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). |
Top K Frequent Elements - Bucket Sort - Leetcode 347 - Python • NeetCode • 665,789 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