LeetCode 3159 - Find Occurrences of an Element in an Array

The problem gives us three inputs: - An integer array nums - An integer array queries - An integer x We need to answer each query independently. A query asks for the index of the kth occurrence of the value x inside the array nums.

leetcodemediumarrayhash-table

LeetCode Problem 3159

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

Problem Understanding

The problem gives us three inputs:

  • An integer array nums
  • An integer array queries
  • An integer x

We need to answer each query independently. A query asks for the index of the kth occurrence of the value x inside the array nums.

For example, if:

nums = [1,3,1,7]
x = 1

then the occurrences of 1 appear at indices:

0, 2

This means:

  • The 1st occurrence is at index 0
  • The 2nd occurrence is at index 2
  • The 3rd occurrence does not exist

So if a query asks for the 2nd occurrence, we return 2. If it asks for the 3rd occurrence, we return -1.

The output is an array where each position corresponds to the answer for the matching query.

The constraints are important:

  • nums.length and queries.length can each be as large as 10^5
  • A naive nested scan for every query could become too slow
  • We need an efficient approach that avoids repeatedly scanning the entire array

The problem guarantees that:

  • Query values are positive integers
  • Array values are positive integers
  • Arrays are non-empty

Several edge cases are important:

  • x may not appear in nums at all
  • A query may ask for an occurrence number larger than the total number of occurrences
  • nums may contain only one occurrence of x
  • Every element in nums may equal x

A correct implementation must handle all of these cases efficiently.

Approaches

Brute Force Approach

A straightforward approach is to process each query independently.

For every query k, we scan the entire nums array from left to right while counting occurrences of x. Once we reach the kth occurrence, we return its index. If the scan finishes before reaching k occurrences, we return -1.

This approach is correct because it directly simulates the definition of the problem. However, it is inefficient.

If:

  • n = len(nums)
  • m = len(queries)

then in the worst case we scan all n elements for each of the m queries.

This gives a time complexity of:

O(n * m)

With both values potentially reaching 10^5, this could require up to 10^10 operations, which is far too slow.

Optimal Approach

The key observation is that the positions of x inside nums never change between queries.

Instead of rescanning the array for every query, we can preprocess the array once and store all indices where nums[i] == x.

For example:

nums = [1,3,1,7]
x = 1

We store:

positions = [0, 2]

Now answering a query becomes very easy:

  • Query 1 asks for the 1st occurrence → positions[0]
  • Query 2 asks for the 2nd occurrence → positions[1]
  • Query 3 does not exist because the list length is only 2

This transforms each query into a simple array lookup.

The preprocessing takes one pass through nums, and each query is answered in constant time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Rescans the array for every query
Optimal O(n + m) O(k) Stores indices of all occurrences of x

Here, k is the number of times x appears in nums.

Algorithm Walkthrough

  1. Create an empty list called positions.

This list will store the indices where nums[i] == x. 2. Traverse the nums array from left to right.

For every index i:

  • If nums[i] == x, append i to positions

After this step, positions[j] represents the index of the (j + 1)th occurrence of x. 3. Create an empty result list called answer. 4. Process each query value k.

Since queries are 1-indexed occurrences:

  • The kth occurrence corresponds to positions[k - 1]
  1. Check whether the requested occurrence exists.
  • If k <= len(positions), append positions[k - 1]
  • Otherwise append -1
  1. Return the answer list after processing all queries.

Why it works

The algorithm works because positions stores the indices of all occurrences of x in the exact order they appear in nums.

Since array traversal happens from left to right:

  • positions[0] is the first occurrence
  • positions[1] is the second occurrence
  • and so on

Therefore, the kth occurrence always corresponds to positions[k - 1], provided that index exists. If it does not exist, then fewer than k occurrences are present, so the correct answer is -1.

Python Solution

from typing import List

class Solution:
    def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:
        positions = []

        for index, value in enumerate(nums):
            if value == x:
                positions.append(index)

        answer = []

        for query in queries:
            if query <= len(positions):
                answer.append(positions[query - 1])
            else:
                answer.append(-1)

        return answer

The implementation begins by scanning nums once and collecting every index where the value equals x.

The enumerate() function is useful because it gives both the index and the value during iteration.

After preprocessing, the algorithm processes each query independently. Since queries are 1-indexed, the code accesses positions[query - 1].

Before accessing the list, the implementation checks whether the requested occurrence exists. If the query exceeds the number of stored positions, the answer is -1.

Finally, the completed answer list is returned.

Go Solution

func occurrencesOfElement(nums []int, queries []int, x int) []int {
	positions := []int{}

	for index, value := range nums {
		if value == x {
			positions = append(positions, index)
		}
	}

	answer := make([]int, 0, len(queries))

	for _, query := range queries {
		if query <= len(positions) {
			answer = append(answer, positions[query-1])
		} else {
			answer = append(answer, -1)
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

A slice named positions stores all indices where x appears. The result slice is initialized with capacity equal to the number of queries to reduce reallocations.

Go slices naturally handle dynamic growth with append(), which makes them suitable for this problem.

Integer overflow is not a concern because all values remain well within Go's standard integer range.

Worked Examples

Example 1

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

Step 1: Build the positions list

Index nums[index] Equals x? positions
0 1 Yes [0]
1 3 No [0]
2 1 Yes [0, 2]
3 7 No [0, 2]

Final:

positions = [0, 2]

Step 2: Process queries

Query Meaning Result
1 1st occurrence positions[0] = 0
3 3rd occurrence Does not exist, -1
2 2nd occurrence positions[1] = 2
4 4th occurrence Does not exist, -1

Final answer:

[0, -1, 2, -1]

Example 2

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

Step 1: Build the positions list

No element equals 5.

positions = []

Step 2: Process queries

Query Meaning Result
10 10th occurrence Does not exist, -1

Final answer:

[-1]

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) One pass through nums, one pass through queries
Space O(k) Stores indices of occurrences of x

Here:

  • n is the length of nums
  • m is the length of queries
  • k is the number of occurrences of x

The preprocessing scan is linear in the size of nums. Each query is answered in constant time using direct indexing into the positions list.

The auxiliary space depends only on how many times x appears.

Test Cases

from typing import List

class Solution:
    def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:
        positions = []

        for index, value in enumerate(nums):
            if value == x:
                positions.append(index)

        answer = []

        for query in queries:
            if query <= len(positions):
                answer.append(positions[query - 1])
            else:
                answer.append(-1)

        return answer

solution = Solution()

assert solution.occurrencesOfElement(
    [1,3,1,7],
    [1,3,2,4],
    1
) == [0,-1,2,-1]  # Provided example with mixed valid and invalid queries

assert solution.occurrencesOfElement(
    [1,2,3],
    [10],
    5
) == [-1]  # x does not appear at all

assert solution.occurrencesOfElement(
    [5,5,5,5],
    [1,2,3,4],
    5
) == [0,1,2,3]  # Every element equals x

assert solution.occurrencesOfElement(
    [4,1,2,3],
    [1,2],
    4
) == [0,-1]  # x appears exactly once

assert solution.occurrencesOfElement(
    [1,2,1,2,1],
    [1,2,3],
    1
) == [0,2,4]  # Multiple valid occurrences

assert solution.occurrencesOfElement(
    [9],
    [1],
    9
) == [0]  # Single element array with matching x

assert solution.occurrencesOfElement(
    [9],
    [1],
    1
) == [-1]  # Single element array without matching x

assert solution.occurrencesOfElement(
    [2,2,2],
    [4,5,6],
    2
) == [-1,-1,-1]  # Queries larger than total occurrences

assert solution.occurrencesOfElement(
    [1,2,3,4,5],
    [1],
    5
) == [4]  # Match at final index

Test Case Summary

Test Why
[1,3,1,7] with mixed queries Validates standard behavior
x not present Ensures -1 is returned correctly
All elements equal x Tests dense occurrence storage
Single occurrence Verifies handling of minimal valid count
Multiple valid occurrences Confirms indexing logic
Single element matching Smallest valid input
Single element non-matching Smallest invalid input
Queries larger than occurrence count Tests bounds checking
Match at final index Ensures indices are stored correctly

Edge Cases

One important edge case occurs when x does not appear anywhere in nums. In this situation, the positions list remains empty. A careless implementation might attempt to access elements from an empty list, causing an error. This implementation safely checks whether the requested occurrence exists before indexing, so every query correctly returns -1.

Another important case is when queries request occurrences larger than the total number of matches. For example, if x appears only twice but a query asks for the 10th occurrence, the answer must be -1. The implementation handles this by comparing the query value against len(positions) before accessing the list.

A third edge case involves arrays where every element equals x. In this scenario, the positions list grows to the same size as nums. The implementation still works efficiently because indices are appended in linear time, and each query remains a constant-time lookup.

A final edge case is the smallest possible input size, such as a single-element array. Whether the element matches x or not, the implementation handles both situations naturally because the preprocessing loop and query logic do not depend on any minimum array size beyond one element.