How do you solve Find Occurrences of an Element in an Array on LeetCode?

Find Occurrences of an Element in an Array (LeetCode #3159) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + m) time complexity and O(n) space complexity. Key insight: Precomputing indices allows for faster query responses.

What is the brute force solution for Find Occurrences of an Element in an Array?

The brute force approach for Find Occurrences of an Element in an Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking each query against the entire array to find the occurrences of the target element. This is straightforward but inefficient, especially for large inputs. The optimal Optimal Solution approach improves this to O(n + m).

What algorithm or data structure is used to solve Find Occurrences of an Element in an Array?

Find Occurrences of an Element in an Array uses the following concepts: Array, Hash Table. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Find Occurrences of an Element in an Array?

Always clarify the indexing used in the problem (0-based or 1-based). Discuss your thought process and any edge cases before coding. Optimize your solution only after you have a working brute-force version.

What are common mistakes when solving Find Occurrences of an Element in an Array?

Not considering the case where the element doesn't exist in the array. Failing to account for 0-based vs 1-based indexing in queries.

#3159

Find Occurrences of an Element in an Array

Medium

ArrayHash TableHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n + m)
Space	O(1)	O(n)

💡

Intuition

Time O(n + m)Space O(n)

The optimal approach involves precomputing the indices of all occurrences of x in the nums array. This allows each query to be answered in constant time, significantly improving efficiency.

⚙️

Algorithm

3 steps

1Step 1: Create a list to store indices of occurrences of x in nums.
2Step 2: Iterate through nums and populate the list with indices where x is found.
3Step 3: For each query, check if the requested occurrence exists in the list; if yes, return the index, otherwise return -1.

solution.py3 lines

1def find_occurrences(nums, queries, x):
2    indices = [i for i, num in enumerate(nums) if num == x]
3    return [indices[q - 1] if q - 1 < len(indices) else -1 for q in queries]

ℹ

Complexity note: The time complexity is O(n + m), where n is the length of nums and m is the length of queries. We first scan nums to find occurrences (O(n)) and then answer each query in O(1) time (O(m)).

1Precomputing indices allows for faster query responses.
2Understanding the problem constraints helps in choosing the right approach.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.