Find Occurrences of an Element in an Array
MedPrompt
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 1st query, the first occurrence of 1 is at index 0.
- For the 2nd query, there are only two occurrences of 1 in
nums, so the answer is -1. - For the 3rd query, the second occurrence of 1 is at index 2.
- For the 4th 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 1st query, 5 doesn't exist in
nums, so the answer is -1.
Constraints:
1 <= nums.length, queries.length <= 1051 <= queries[i] <= 1051 <= nums[i], x <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
This is a straightforward, brute-force solution. For each query, we perform a full scan of the nums array from the beginning. We keep a count of the occurrences of x we've seen so far. When the count matches the desired occurrence number from the query, we record the current index and move to the next query. If we scan the entire array and don't find the required number of occurrences, the answer for that query is -1.
Algorithm
- Initialize an integer array
answerwith the same length asqueries. - Iterate through each query
kat indexiin thequeriesarray. - For each
k, initialize a countercountto 0 and a variablefoundIndexto -1. - Iterate through the
numsarray from left to right with indexj. - If
nums[j]is equal to the target valuex, incrementcount. - If
countbecomes equal tok, it means we have found thek-th occurrence. SetfoundIndexto the current indexjand break the inner loop. - After the inner loop finishes, assign
foundIndextoanswer[i]. - After iterating through all queries, return the
answerarray.
Walkthrough
The core idea is to process each query independently. For a query asking for the k-th occurrence, we iterate through nums and count how many times we've encountered x. When our count reaches k, the index at that point is our answer. This process is repeated for every single query in the queries array.
class Solution { public int[] occurrencesOfElement(int[] nums, int[] queries, int x) { int[] answer = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int k = queries[i]; int count = 0; int foundIndex = -1; for (int j = 0; j < nums.length; j++) { if (nums[j] == x) { count++; if (count == k) { foundIndex = j; break; // Found the k-th occurrence, no need to search further for this query } } } answer[i] = foundIndex; } return answer; }}Complexity
Time
O(N * Q), where N is the length of `nums` and Q is the length of `queries`. In the worst-case scenario, for each of the Q queries, we may need to traverse the entire `nums` array.
Space
O(Q) to store the answer array. Excluding the output array, the space complexity is O(1) as we only use a few variables to process each query.
Trade-offs
Pros
Simple to understand and implement.
Uses O(1) extra space (if the output array is not considered).
Cons
Extremely inefficient for large inputs due to its nested loop structure.
The time complexity is quadratic, O(N * Q), which will lead to a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode given the problem constraints.
Solutions
Solution
class Solution {public int[] occurrencesOfElement(int[] nums, int[] queries, int x) { List<Integer> ids = new ArrayList<>(); for (int i = 0; i < nums.length; ++i) { if (nums[i] == x) { ids.add(i); } } int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; ++i) { int j = queries[i] - 1; ans[i] = j < ids.size() ? ids.get(j) : -1; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.