Find Occurrences of an Element in an Array

Find Occurrences of an Element in an Array

What is this problem about?

The Find Occurrences of an Element in an Array interview question is a query-based task. You are given an array nums, a target value x, and a set of queries. Each query $q$ asks for the index of the $q^{th}$ occurrence of x in the array. If x appears fewer than $q$ times, you should return -1 for that query. This Find Occurrences coding problem is about pre-processing data to handle multiple lookups efficiently.

Why is this asked in interviews?

Companies like J.P. Morgan and IBM use this to test your ability to move beyond $O(N)$ searches for every query. It evaluations whether you can identify that a single pass over the array can store all necessary information in a Hash Table interview pattern or a simple list, turning subsequent queries into $O(1)$ operations.

Algorithmic pattern used

This problem follows the Pre-processing with a List/Map pattern.

1. Identify Indices: Iterate through the array once and collect all indices where arr[i] == x.
2. Storage: Store these indices in a separate list (e.g., posList).
3. Query Handling: For each query $q$:
   • If $q$ is greater than the size of posList, return -1.
   • Otherwise, return posList[q - 1] (using 0-based indexing for the list).

Example explanation

Array: [1, 3, 1, 7, 1, 2], target $x = 1$, Queries: [1, 3, 4]

1. Find all '1's: indices are [0, 2, 4].
2. Query 1: $1^{st}$ occurrence is at index 0.
3. Query 2: $3^{rd}$ occurrence is at index 4.
4. Query 3: $4^{th}$ occurrence? Only three '1's exist. Return -1. Result: [0, 4, -1].

Common mistakes candidates make

• Linear Search per Query: Iterating through the entire array for every single query ($O(N imes Q)$), which is highly inefficient if $Q$ is large.
• Off-by-one: Confusing the $1^{st}$ occurrence (rank) with the $0^{th}$ index of the list.
• Memory Management: Storing indices for all elements when the problem only asks for occurrences of a specific $x$.

Interview preparation tip

Always ask the interviewer about the number of queries. If there are many queries, pre-processing the data into an $O(1)$ lookup structure is almost always the expected Array interview pattern solution.