Problem Description

You are given three inputs: an integer array nums, an integer array queries, and an integer x.

Your task is to process each value in the queries array. For each queries[i], you need to find where the queries[i]-th occurrence of the value x appears in the nums array (using 1-based counting for occurrences).

For example, if queries[i] = 3, you need to find the index position of the 3rd time that x appears in nums.

If x doesn't appear at least queries[i] times in the array, return -1 for that particular query.

The final output should be an array answer where each element corresponds to the result of processing each query in order.

Example walkthrough:

• If nums = [1, 3, 1, 7], x = 1, and queries = [1, 2, 3]
• The value 1 appears at indices 0 and 2 (1st and 2nd occurrences)
• For queries[0] = 1: find the 1st occurrence of 1 → index 0
• For queries[1] = 2: find the 2nd occurrence of 1 → index 2
• For queries[2] = 3: find the 3rd occurrence of 1 → doesn't exist → -1
• Result: [0, 2, -1]

Intuition

The key insight is that we need to efficiently map occurrence numbers to their actual positions in the array. Instead of searching through the array multiple times for each query, we can preprocess the information we need.

Think about what we're really asking: "Where is the 1st occurrence of x? Where is the 2nd occurrence? Where is the 3rd occurrence?" This suggests we should collect all positions where x appears and store them in order.

By traversing nums once and collecting all indices where nums[i] == x, we create a list that directly maps occurrence numbers to their positions. For instance, if x appears at indices [2, 5, 8], then:

• The 1st occurrence is at index 2 (position 0 in our list)
• The 2nd occurrence is at index 5 (position 1 in our list)
• The 3rd occurrence is at index 8 (position 2 in our list)

This preprocessing step transforms our problem into a simple array lookup. For each query asking for the k-th occurrence, we just need to check if we have at least k occurrences (by checking if k-1 < len(ids)), and if so, return ids[k-1] (using k-1 because of 0-based indexing).

This approach is efficient because we only scan through nums once to build our occurrence list, and then each query is answered in constant time with a simple array access.

Solution Approach

The solution follows a two-step approach:

Step 1: Collect all occurrences of x

We traverse the nums array once and record the indices where the value equals x:

ids = [i for i, v in enumerate(nums) if v == x]

This list comprehension iterates through nums with both index (i) and value (v), keeping only the indices where v == x. The resulting ids array contains all positions where x appears, in order.

For example, if nums = [1, 3, 1, 7, 1] and x = 1, then ids = [0, 2, 4].

Step 2: Process each query

For each query value i in queries, we need to find the i-th occurrence (1-based):

return [ids[i - 1] if i - 1 < len(ids) else -1 for i in queries]

This list comprehension processes each query by:

• Converting from 1-based to 0-based indexing: i - 1
• Checking if this occurrence exists: i - 1 < len(ids)
• If it exists, returning ids[i - 1] (the actual index in the original array)
• If it doesn't exist, returning -1

Time Complexity: O(n + q) where n is the length of nums and q is the length of queries. We scan nums once and process each query in constant time.

Space Complexity: O(k) where k is the number of occurrences of x in nums, needed to store the ids array.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• nums = [2, 7, 2, 5, 2, 7, 2]
• x = 2
• queries = [1, 3, 4, 5]

Step 1: Collect all occurrences of x = 2

We traverse through nums and record every index where we find the value 2:

• Index 0: nums[0] = 2 ✓ (matches x)
• Index 1: nums[1] = 7 ✗
• Index 2: nums[2] = 2 ✓ (matches x)
• Index 3: nums[3] = 5 ✗
• Index 4: nums[4] = 2 ✓ (matches x)
• Index 5: nums[5] = 7 ✗
• Index 6: nums[6] = 2 ✓ (matches x)

So our ids array becomes: [0, 2, 4, 6]

This tells us:

• 1st occurrence of 2 is at index 0
• 2nd occurrence of 2 is at index 2
• 3rd occurrence of 2 is at index 4
• 4th occurrence of 2 is at index 6

Step 2: Process each query

Now we process each value in queries = [1, 3, 4, 5]:

• queries[0] = 1: Find the 1st occurrence of 2

  • Convert to 0-based index: 1 - 1 = 0
  • Check if valid: 0 < 4 (length of ids) ✓
  • Return ids[0] = 0

• queries[1] = 3: Find the 3rd occurrence of 2

  • Convert to 0-based index: 3 - 1 = 2
  • Check if valid: 2 < 4 ✓
  • Return ids[2] = 4

• queries[2] = 4: Find the 4th occurrence of 2

  • Convert to 0-based index: 4 - 1 = 3
  • Check if valid: 3 < 4 ✓
  • Return ids[3] = 6

• queries[3] = 5: Find the 5th occurrence of 2

  • Convert to 0-based index: 5 - 1 = 4
  • Check if valid: 4 < 4 ✗ (we only have 4 occurrences)
  • Return -1

Final Result: [0, 4, 6, -1]

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The time complexity consists of two main operations:

• Creating the ids list requires iterating through the entire nums array once, which takes O(n) time where n is the length of nums
• Creating the result list requires iterating through all queries and performing constant-time index access for each query, which takes O(m) time where m is the length of queries
• Total time complexity: O(n) + O(m) = O(n + m)

Space Complexity: O(n + m)

The space complexity consists of:

• The ids list can store at most n elements (in the worst case where all elements in nums equal x), requiring O(n) space
• The result list stores exactly m elements (one result for each query), requiring O(m) space
• Total space complexity: O(n) + O(m) = O(n + m)

Where n is the length of the array nums and m is the length of the array queries.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing 1-based vs 0-based indexing

The most common mistake is forgetting that the queries use 1-based counting for occurrences while Python arrays use 0-based indexing.

Incorrect approach:

# Wrong - directly using query value as index
return [occurrence_indices[q] if q < len(occurrence_indices) else -1 for q in queries]

This would cause off-by-one errors. When queries[i] = 1 (asking for the 1st occurrence), we need occurrence_indices[0], not occurrence_indices[1].

Correct approach:

# Correct - subtract 1 to convert from 1-based to 0-based
return [occurrence_indices[q - 1] if q - 1 < len(occurrence_indices) else -1 for q in queries]

2. Handling edge case when x doesn't exist in nums

If x never appears in nums, the occurrence_indices list will be empty. Any query would then need to return -1.

Potential issue:

# This could crash if occurrence_indices is empty and we don't check bounds properly
result.append(occurrence_indices[query - 1])  # IndexError if list is empty

Solution: Always check the bounds before accessing:

if query - 1 < len(occurrence_indices):
    result.append(occurrence_indices[query - 1])
else:
    result.append(-1)

3. Query value of 0 or negative numbers

Though not typically expected based on the problem description, if a query value is 0 or negative, it could cause unexpected behavior.

Example issue:

# If queries[i] = 0, then query - 1 = -1
# Python allows negative indexing, so occurrence_indices[-1] would return the last element!

Solution: Add validation if needed:

if query <= 0 or query - 1 >= len(occurrence_indices):
    result.append(-1)
else:
    result.append(occurrence_indices[query - 1])

4. Memory optimization misconception

Some might try to optimize by not storing all occurrences, instead counting on-the-fly for each query:

Inefficient approach:

def process_query(nums, x, occurrence_num):
    count = 0
    for i, val in enumerate(nums):
        if val == x:
            count += 1
            if count == occurrence_num:
                return i
    return -1

# This would be O(n * q) time complexity - much worse!

The pre-computation approach with stored indices is actually more efficient for multiple queries.