Find Occurrences of an Element in an Array — Solution
Find Occurrences of an Element in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find Occurrences of an Element in an Array is a medium coding problem on arrays and hash table, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums, an integer array queries and an integer x.
For each queries[i], find the index of the queries[i]-th occurrence of x in nums (counting occurrences from 1, left to right). If x occurs fewer than queries[i] times, the answer is -1.
Return an array answer with the answers to all the queries, in order.
Example 1
Input: nums = [1,3,1,7], queries = [1,3,2,4], x = 1
Output: [0,-1,2,-1]
Explanation: 1 occurs at indices 0 and 2, so the 1st occurrence is at 0, the 2nd at 2, and there is no 3rd or 4th.
Example 2
Input: nums = [1,2,3], queries = [10], x = 5
Output: [-1]
Explanation: 5 never occurs.
Example 3
Input: nums = [4,4,4], queries = [3,1,2,3], x = 4
Output: [2,0,1,2]
Constraints
1 <= nums.length, queries.length <= 10^51 <= queries[i] <= 10^51 <= nums[i], x <= 10^4
Hints for Find Occurrences of an Element in an Array
Hint 1
Scanning
numsonce per query is too slow for 10^5 queries.Hint 2
Collect, in one pass, the list of indices where
nums[i] == x, in increasing order.Hint 3
The
q-th occurrence is then simply elementq - 1of that list, if the list is long enough.
How to solve Find Occurrences of an Element in an Array
Precompute the positions of x in order; every query is then an array lookup.
Approach
- Scan
numsand append every indexiwithnums[i] == xto a listpos. - For each query
q, answerpos[q - 1]ifq <= pos.length, otherwise-1.
Why it works
pos lists the occurrences of x left to right, so its (q - 1)-th entry (0-based) is by definition the q-th occurrence; a shorter list means there are fewer than q occurrences.
Complexity
- Time —
O(n + q) - Space —
O(n)
Pitfalls
- Queries are 1-based: the 1st occurrence is
pos[0]. - Queries can be far larger than the number of occurrences — check the bound before indexing.
Reference solution
Python
from typing import List
def occurrencesOfElement(nums: List[int], queries: List[int], x: int) -> List[int]:
pos = [i for i, v in enumerate(nums) if v == x]
return [pos[q - 1] if q <= len(pos) else -1 for q in queries]Java
public static int[] occurrencesOfElement(int[] nums, int[] queries, int x) {
int[] pos = new int[nums.length];
int k = 0;
for (int i = 0; i < nums.length; i++) if (nums[i] == x) pos[k++] = i;
int[] out = new int[queries.length];
for (int j = 0; j < queries.length; j++) out[j] = queries[j] <= k ? pos[queries[j] - 1] : -1;
return out;
}C++
vector<int> occurrencesOfElement(vector<int>& nums, vector<int>& queries, int x) {
vector<int> pos;
for (int i = 0; i < (int) nums.size(); i++) if (nums[i] == x) pos.push_back(i);
vector<int> out;
out.reserve(queries.size());
for (int q : queries) out.push_back(q <= (int) pos.size() ? pos[q - 1] : -1);
return out;
}JavaScript
var occurrencesOfElement = function(nums, queries, x) {
var pos = [];
for (var i = 0; i < nums.length; i++) if (nums[i] === x) pos.push(i);
var out = [];
for (var j = 0; j < queries.length; j++) out.push(queries[j] <= pos.length ? pos[queries[j] - 1] : -1);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets