#3159

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Occurrences of an Element in an Array

Determine the position of each requested occurrence of x in nums using a hash table and efficient array scanning.

Problem Statement

You are given an integer array nums, an integer array queries, and an integer x. For each queries[i], determine the index in nums where x appears for the queries[i]th time. If nums contains fewer than queries[i] occurrences of x, return -1 for that query.

Return an array answer where answer[i] corresponds to the result for queries[i]. Optimize your solution by scanning nums once and storing occurrence indices to handle all queries quickly.

Examples

Example 1

Input: nums = [1,3,1,7], queries = [1,3,2,4], x = 1

Output: [0,-1,2,-1]

Example 2

Input: nums = [1,2,3], queries = [10], x = 5

Output: [-1]

Constraints

1 <= nums.length, queries.length <= 105
1 <= queries[i] <= 105
1 <= nums[i], x <= 104

Solution Approach

Preprocess occurrences with hash map

Scan nums once and maintain a hash map where the key is the number x and the value is a list of indices where x appears. This reduces repeated scanning when answering multiple queries.

Answer each query efficiently

For each queries[i], check the list of indices for x in the hash map. If the list length is less than queries[i], return -1; otherwise, return the index at position queries[i]-1.

Optimize space and access

Compress storage by only saving indices for numbers that appear in queries or the target x. This saves memory and improves cache efficiency for large arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + q) where n is nums length and q is queries length, because nums is scanned once and each query is answered in O(1). Space complexity is O(n) in the worst case for storing all occurrence indices of x.

What Interviewers Usually Probe

Check if candidates precompute occurrence indices or scan nums repeatedly.
Listen for hash map usage versus naive iteration for multiple queries.
Notice if candidates handle edge cases when occurrences are fewer than query values.

Common Pitfalls or Variants

Common pitfalls

Repeatedly scanning nums for each query causing TLE on large inputs.
Not handling zero-based indexing properly for queries[i]th occurrence.
Assuming every query is valid without checking if x occurs enough times.

Follow-up variants

Count the number of occurrences instead of returning the index.
Return all indices for multiple target values in a single query array.
Find last k occurrences of x instead of the first k occurrences.

FAQ

What is the most efficient way to find the k-th occurrence of x in nums?

Use a hash map to store all indices of x during a single scan of nums, then answer each query in O(1) time.

What happens if queries[i] is larger than the number of occurrences of x?

Return -1 for that query because the requested occurrence does not exist in nums.

Can this problem be solved without a hash map?

Yes, but scanning nums for each query leads to O(n*q) time which is inefficient for large arrays.

How do I handle multiple queries efficiently?

Precompute a list of all positions where x appears, then access each queries[i]-1 index directly.

Why is this problem categorized under Array scanning plus hash lookup?

Because the optimal solution combines scanning nums once to build a hash map with lists of indices for quick query resolution.

terminal

Solution

Solution 1: 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`.

1

2

3

4

5

6

class Solution:
    def occurrencesOfElement(
        self, nums: List[int], queries: List[int], x: int
    ) -> List[int]:
        ids = [i for i, v in enumerate(nums) if v == x]
        return [ids[i - 1] if i - 1 < len(ids) else -1 for i in queries]

Continue Practicing

#3158 find the xor of numbers which appear twice #3160 find the number of distinct colors among the balls #3162 find the number of good pairs i