Find Occurrences of an Element in an Array solution and explanation
IBM
9 more videos on this problem
Leetcode 3159 | Find Occurrences of an Element in an Array | Leetcode Biweekly Contest 131Road To FAANG · 7:29 · 598 views
3159. Find Occurrences of an Element in an Array | Map | Medium | Array | LeetCodeLeet's Code · 8:41 · 527 views
3159. Find Occurrences of an Element in an ArrayTech Courses · 5:02 · 498 views
3159. Find Occurrences of an Element in an Array (Leetcode Medium)Programming Live with Larry · 4:16 · 338 views
🔍 Find Occurrences of an Element in an Array | LeetCode 3159 🎥Adarsh Dubey · 6:49 · 288 views
3159. Find Occurrences of an Element in an Array || Leetcode 3159 solution in C++Mukto Academy Global · 5:13 · 143 views
3159. Find Occurrences of an Element in an Array #java #array #leetcode #dsa #coding #array #dsaCodeVia · 2:50 · 113 views
100303 Find Occurrences of an Element in an Array | leetcode | java | biweekly 131 | solved |Ssquare · 1:21 · 82 views
Find Occurrences of an Element in an Array | Leetcode 3159 | Explanation With Code | Javacodewithsitaram · 18:52 · 56 views
DECODEDSA#LEVELUP#CONTESTSOL#leetcode#challenge3159. Find Occurrences of an Element in an ArrayDecode · 7:28 · 53 views
The problem
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
Approach overview
Problem 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 1: Naive Linear Search
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.
def find_occurrences(nums, queries, x):
answer = [-1] * len(queries)
for i, query in enumerate(queries):
occurrence = 0
for j, num in enumerate(nums):
if num == x:
occurrence += 1
if occurrence == query:
answer[i] = j
break
return answer
nums = [1, 3, 1, 7]
queries = [1, 3, 2, 4]
x = 1
print(find_occurrences(nums, queries, x))import java.util.*;
public class Solution {
public static int[] findOccurrences(int[] nums, int[] queries, int x) {
int[] answer = new int[queries.length];
Arrays.fill(answer, -1);
for (int i = 0; i < queries.length; i++) {
int occurrence = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[j] == x) {
occurrence++;
if (occurrence == queries[i]) {
answer[i] = j;
break;
}
}
}
}
return answer;
}
public static void main(String[] args) {
int[] nums = {1, 3, 1, 7};
int[] queries = {1, 3, 2, 4};
int x = 1;
int[] result = findOccurrences(nums, queries, x);
System.out.println(Arrays.toString(result));
}
}#include <vector>
#include <iostream>
std::vector<int> findOccurrences(const std::vector<int>& nums, const std::vector<int>& queries, int x) {
std::vector<int> answer(queries.size(), -1);
for (size_t i = 0; i < queries.size(); ++i) {
int occurrence = 0;
for (size_t j = 0; j < nums.size(); ++j) {
if (nums[j] == x) {
occurrence++;
if (occurrence == queries[i]) {
answer[i] = j;
break;
}
}
}
}
return answer;
}
int main() {
std::vector<int> nums = {1, 3, 1, 7};
std::vector<int> queries = {1, 3, 2, 4};
int x = 1;
std::vector<int> result = findOccurrences(nums, queries, x);
for (int i : result) {
std::cout << i << " ";
}
return 0;
}function findOccurrences(nums, queries, x) {
const answer = Array(queries.length).fill(-1);
queries.forEach((query, i) => {
let occurrence = 0;
for (let j = 0; j < nums.length; j++) {
if (nums[j] === x) {
occurrence++;
if (occurrence === query) {
answer[i] = j;
break;
}
}
}
});
return answer;
}
const nums = [1, 3, 1, 7];
const queries = [1, 3, 2, 4];
const x = 1;
console.log(findOccurrences(nums, queries, x));#include <stdio.h>
void findOccurrences(int *nums, int numsSize, int *queries, int queriesSize, int x, int *answer) {
for (int i = 0; i < queriesSize; i++) {
int occurrence = 0, foundIndex = -1;
for (int j = 0; j < numsSize; j++) {
if (nums[j] == x) {
occurrence++;
if (occurrence == queries[i]) {
foundIndex = j;
break;
}
}
}
answer[i] = foundIndex;
}
}
int main() {
int nums[] = {1, 3, 1, 7};
int queries[] = {1, 3, 2, 4};
int x = 1;
int answer[4];
findOccurrences(nums, 4, queries, 4, x, answer);
for (int i = 0; i < 4; i++) {
printf("%d ", answer[i]);
}
return 0;
}using System;
public class Solution {
public static int[] FindOccurrences(int[] nums, int[] queries, int x) {
int[] answer = new int[queries.Length];
for (int i = 0; i < queries.Length; i++) {
int occurrence = 0;
answer[i] = -1;
for (int j = 0; j < nums.Length; j++) {
if (nums[j] == x) {
occurrence++;
if (occurrence == queries[i]) {
answer[i] = j;
break;
}
}
}
}
return answer;
}
public static void Main() {
int[] nums = {1, 3, 1, 7};
int[] queries = {1, 3, 2, 4};
int x = 1;
int[] result = FindOccurrences(nums, queries, x);
Console.WriteLine(String.Join(" ", result));
}
}The Python solution uses a list answer initialized to -1. It iterates over queries and the nums array, counting occurrences of x to find the desired index or return -1.
Time Complexity: O(q * n).
Space Complexity: O(1).
Approach 2: Preprocessing with Index Mapping
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.
def find_occurrences(nums, queries, x):
index_map = [i for i, num in enumerate(nums) if num == x]
return [index_map[query - 1] if query <= len(index_map) else -1 for query in queries]
nums = [1, 3, 1, 7]
queries = [1, 3, 2, 4]
x = 1
print(find_occurrences(nums, queries, x))import java.util.*;
public class Solution {
public static int[] findOccurrences(int[] nums, int[] queries, int x) {
List<Integer> indexMap = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] == x) {
indexMap.add(i);
}
}
int[] answer = new int[queries.length];
Arrays.fill(answer, -1);
for (int i = 0; i < queries.length; i++) {
if (queries[i] <= indexMap.size()) {
answer[i] = indexMap.get(queries[i] - 1);
}
}
return answer;
}
public static void main(String[] args) {
int[] nums = {1, 3, 1, 7};
int[] queries = {1, 3, 2, 4};
int x = 1;
int[] result = findOccurrences(nums, queries, x);
System.out.println(Arrays.toString(result));
}
}#include <vector>
#include <iostream>
std::vector<int> findOccurrences(const std::vector<int>& nums, const std::vector<int>& queries, int x) {
std::vector<int> indexMap;
for (size_t i = 0; i < nums.size(); ++i) {
if (nums[i] == x) {
indexMap.push_back(i);
}
}
std::vector<int> answer(queries.size(), -1);
for (size_t i = 0; i < queries.size(); ++i) {
if (queries[i] <= indexMap.size()) {
answer[i] = indexMap[queries[i] - 1];
}
}
return answer;
}
int main() {
std::vector<int> nums = {1, 3, 1, 7};
std::vector<int> queries = {1, 3, 2, 4};
int x = 1;
std::vector<int> result = findOccurrences(nums, queries, x);
for (int i : result) {
std::cout << i << " ";
}
return 0;
}function findOccurrences(nums, queries, x) {
const indexMap = nums.reduce((acc, num, idx) => {
if (num === x) acc.push(idx);
return acc;
}, []);
return queries.map(query => query <= indexMap.length ? indexMap[query - 1] : -1);
}
const nums = [1, 3, 1, 7];
const queries = [1, 3, 2, 4];
const x = 1;
console.log(findOccurrences(nums, queries, x));#include <stdio.h>
#include <stdlib.h>
void findOccurrences(int *nums, int numsSize, int *queries, int queriesSize, int x, int *answer) {
int *indexMap = (int *)malloc(numsSize * sizeof(int));
int indexCount = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == x) {
indexMap[indexCount++] = i;
}
}
for (int i = 0; i < queriesSize; i++) {
if (queries[i] <= indexCount) {
answer[i] = indexMap[queries[i] - 1];
} else {
answer[i] = -1;
}
}
free(indexMap);
}
int main() {
int nums[] = {1, 3, 1, 7};
int queries[] = {1, 3, 2, 4};
int x = 1;
int answer[4];
findOccurrences(nums, 4, queries, 4, x, answer);
for (int i = 0; i < 4; i++) {
printf("%d ", answer[i]);
}
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public static int[] FindOccurrences(int[] nums, int[] queries, int x) {
List<int> indexMap = new List<int>();
for (int i = 0; i < nums.Length; i++) {
if (nums[i] == x) {
indexMap.Add(i);
}
}
int[] answer = new int[queries.Length];
for (int i = 0; i < queries.Length; i++) {
if (queries[i] <= indexMap.Count) {
answer[i] = indexMap[queries[i] - 1];
} else {
answer[i] = -1;
}
}
return answer;
}
public static void Main() {
int[] nums = {1, 3, 1, 7};
int[] queries = {1, 3, 2, 4};
int x = 1;
int[] result = FindOccurrences(nums, queries, x);
Console.WriteLine(String.Join(" ", result));
}
}The Python implementation computes positions of x at initialization. Each query uses precomputed results stored in index_map allowing O(1) complexity for processing.
Time Complexity: O(n + q).
Space Complexity: O(n) due to stored positions in index_map.
Approach 3: Simulation
According to the problem description, we can first traverse the array nums to find the indices of all elements with a value of x, and record them in the array ids.
Next, we traverse the array queries. For each query i, if i - 1 is less than the length of ids, then the answer is ids[i - 1], otherwise, the answer is -1.
The time complexity is O(n + m), and the space complexity is O(n + m). Where n and m are the lengths of the arrays nums and queries respectively.
function occurrencesOfElement(nums: number[], queries: number[], x: number): number[] {
const ids: number[] = nums.map((v, i) => (v === x ? i : -1)).filter(v => v !== -1);
return queries.map(i => ids[i - 1] ?? -1);
}func occurrencesOfElement(nums []int, queries []int, x int) (ans []int) {
ids := []int{}
for i, v := range nums {
if v == x {
ids = append(ids, i)
}
}
for _, i := range queries {
if i-1 < len(ids) {
ans = append(ans, ids[i-1])
} else {
ans = append(ans, -1)
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Linear Search | Time Complexity: O(q * n). |
| Preprocessing with Index Mapping | Time Complexity: O(n + q). |
| Simulation | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find Occurrences of an Element in an Array easy or hard?
The problem is rated Medium because the brute-force solution is simple but inefficient for many queries. Recognizing the need for preprocessing with a hash map and storing indices is the key insight that leads to the optimal solution.
Find Occurrences of an Element in an Array Python/Java solution
In Python, use a dictionary mapping values to lists of indices and return list[k-1] if it exists. In Java, use a HashMap<Integer, List<Integer>> to store occurrence indices and answer queries in constant time.
How to solve Find Occurrences of an Element in an Array in O(n)?
Build a hash map that stores the indices of every occurrence of each value during a single pass through the array. After preprocessing, answering a query for the k-th occurrence simply checks the stored list and returns the element at index k-1 if it exists.
What is the best approach for Find Occurrences of an Element in an Array?
The most efficient approach is preprocessing with index mapping. Traverse the array once and store all indices of each value in a hash map. Each query then retrieves the k-th occurrence directly from the stored list in O(1) time, resulting in O(n + q) total complexity.
Is Find Occurrences of an Element in an Array asked at Google/Amazon/Meta?
Problems involving occurrence indexing and preprocessing arrays appear frequently in interviews at large tech companies. Variations of this pattern show up at companies like Amazon and Google where candidates must optimize repeated queries over static data.
What data structure is used in Find Occurrences of an Element in an Array?
The optimized solution uses a hash table (dictionary) that maps each value to a list of indices where it appears. This structure allows constant-time lookup of the k-th occurrence after preprocessing.
What is the time complexity of Find Occurrences of an Element in an Array?
The naive solution takes O(n * q) time because the array is scanned for every query. The optimized approach preprocesses the array in O(n) and answers each query in O(1), giving an overall time complexity of O(n + q).