Skip to main content
Talentd

Find Occurrences of an Element in an Array - Solution & Explanation

MediumArrayHash Table16 min readAsked at: Amazon, IBM, Jpmorgan
Practice this problem

Problem Statement

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 <= 105
  • 1 <= queries[i] <= 105
  • 1 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(q * n) where q is the size of queries and n is the size of nums.
Space Complexity: O(1).

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + q).
Space Complexity: O(n) for the index map.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Linear Search

Time Complexity: O(q * n) where q is the size of queries and n is the size of nums.
Space Complexity: O(1).

Preprocessing with Index Mapping

Time Complexity: O(n + q).
Space Complexity: O(n) for the index map.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Linear SearchO(n * q)O(1)When queries are few or input size is small
Preprocessing with Index MappingO(n + q)O(n)Best general solution when many queries must be answered quickly

Video Solution

Leetcode 3159 | Find Occurrences of an Element in an Array | Leetcode Biweekly Contest 131 • Road To FAANG • 598 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Find Occurrences of an Element in an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays