3159. Find Occurrences of an Element in an Array

MediumArrayHash Table

Problem Description

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

For each queries[i], you need to determine the index of the queries[i]^th occurrence of x in the nums array. If there are fewer than queries[i] occurrences of x, the answer should be -1 for that query.

Return an integer array answer containing the responses to all queries.

Intuition

The task is to find the specific occurrence of a given integer x in the array nums for each query and return the index of that occurrence. The key insight is to first identify and record all indices where x occurs in nums. By doing this, we can quickly access any desired occurrence within these recorded indices.

Here's how we approach the solution:

Traverse the Array: First, scan through the nums array to collect all indices where x appears. Store these indices in a list called ids.
Process Queries: For each query in the queries array, check whether the desired occurrence index (queries[i] - 1 due to zero-based indexing) exists in the ids list. If it does, append that index from the ids list to the result. If not, append -1 to denote that the desired occurrence is unavailable.

This method efficiently handles multiple queries by precomputing the indices of x occurrences, allowing for quick lookup and decision-making for each query.

Solution Approach

The solution involves utilizing a simulation strategy to efficiently address the problem:

Find Occurrences of x:
- Traverse the nums array and identify indices where the value equals x. This is done using a list comprehension:
```
ids = [i for i, v in enumerate(nums) if v == x]
```
Here, enumerate helps to track both the index and value of elements in nums, allowing us to build a list ids containing all indices where x is found.
Process Each Query:
- Iterate over each query in the queries array. For each query:
  - Check if the desired occurrence (queries[i]) is available by comparing it to the length of the ids list.
  - If the occurrence exists (i - 1 < len(ids)), retrieve the index of this occurrence from ids. Otherwise, return -1.
- This can be handled in a compact form using another list comprehension:
```
return [ids[i - 1] if i - 1 < len(ids) else -1 for i in queries]
```

This approach is efficient because it separates the concerns of finding and processing occurrences. The list of indices, ids, acts as a simple lookup table for resolving queries quickly. This separation ensures clarity and minimizes redundant operations across queries.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

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

Example

Suppose nums = [1, 2, 3, 2, 4, 2, 5], queries = [1, 2, 3, 4], and x = 2.

Step 1: Find Occurrences of x

First, we traverse the array nums to find indices where the value equals x (which is 2 in this case). We collect these indices in list ids.

At index 1, nums[1] = 2, so we add 1 to ids.
At index 3, nums[3] = 2, so we add 3 to ids.
At index 5, nums[5] = 2, so we add 5 to ids.

Thus, ids = [1, 3, 5].

Step 2: Process Each Query

Next, we process each query to determine the desired occurrence of x in nums using the ids list.

For queries[0] = 1: We need the 1st occurrence of x. Since ids has 3 elements, we check ids[0] and get the value 1. Thus, for this query, the result is 1.
For queries[1] = 2: We need the 2nd occurrence of x. Comparing against ids, this corresponds to ids[1], which is 3. Therefore, the result for this query is 3.
For queries[2] = 3: We need the 3rd occurrence of x. This corresponds to ids[2], which is 5, hence the result is 5.
For queries[3] = 4: We seek the 4th occurrence of x. However, ids only contains indices for the first 3 occurrences (i.e., less than 4), so the answer is -1.

Combining these results, we obtain answer = [1, 3, 5, -1].

In summary, by precomputing the indices of x occurrences in nums, we efficiently resolve each query based on available occurrences.

Solution Implementation

1from typing import List
2
3class Solution:
4    def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:
5        # Find the indices where the element x appears in nums
6        indices = [i for i, value in enumerate(nums) if value == x]
7      
8        # For each query, return the index of the (query-1)th occurrence of x
9        return [indices[query - 1] if query - 1 < len(indices) else -1 for query in queries]
10

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {
6        List<Integer> indices = new ArrayList<>(); // List to store indices where nums[i] is equal to x
7      
8        // Populate the list with indices of nums where element equals x
9        for (int i = 0; i < nums.length; ++i) {
10            if (nums[i] == x) {
11                indices.add(i);
12            }
13        }
14
15        int queryCount = queries.length; // Number of queries
16        int[] result = new int[queryCount]; // Array to store the result for each query
17      
18        // Process each query
19        for (int i = 0; i < queryCount; ++i) {
20            int queryIndex = queries[i] - 1; // Convert 1-based query to 0-based index for accessing list
21            // If the query index is within the bounds of the list, get the value, else return -1
22            result[i] = queryIndex < indices.size() ? indices.get(queryIndex) : -1;
23        }
24      
25        return result; // Return the resulting array
26    }
27}
28

1#include <vector>
2
3class Solution {
4public:
5    std::vector<int> occurrencesOfElement(std::vector<int>& nums, std::vector<int>& queries, int x) {
6        std::vector<int> indices;
7      
8        // Collect indices of the element 'x' in the 'nums' array.
9        for (int i = 0; i < nums.size(); ++i) {
10            if (nums[i] == x) {
11                indices.push_back(i);
12            }
13        }
14      
15        std::vector<int> result;
16      
17        // Process each query.
18        for (int& query : queries) {
19            // Check if the query is valid (query - 1 should be within the range of 'indices').
20            if (query - 1 < indices.size()) {
21                result.push_back(indices[query - 1]); // Add the corresponding index to the result.
22            } else {
23                result.push_back(-1); // If invalid, add -1 to the result.
24            }
25        }
26      
27        return result; // Return the result containing indices or -1.
28    }
29};
30

1// Function to find the occurrences of a specific element 'x' in an array 'nums'
2// and return the indices of these occurrences based on 'queries'.
3function occurrencesOfElement(nums: number[], queries: number[], x: number): number[] {
4    // Create an array 'ids' to store indices where the element 'x' occurs in 'nums'
5    const ids: number[] = nums.map((value, index) => (value === x ? index : -1)).filter(index => index !== -1);
6
7    // Map each query to find the corresponding index of the occurrence
8    // Return -1 if the query index is out of bounds
9    return queries.map(queryIndex => ids[queryIndex - 1] ?? -1);
10}
11

Time and Space Complexity

The time complexity of the code is O(n + m). This is because:

The list comprehension [i for i, v in enumerate(nums) if v == x] iterates over the entire list nums once, which takes O(n) time.
The second list comprehension [ids[i - 1] if i - 1 < len(ids) else -1 for i in queries] iterates over the entire list queries, taking O(m) time.

Thus, the combined time complexity is O(n + m).

The space complexity of the code is O(n + m) because:

The list ids stores indices of elements equal to x, which can be at most O(n) in size.
The resulting list from the second comprehension is O(m) in size.

Therefore, the space complexity is O(n + m).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What data structure does Breadth-first search typically uses to store intermediate states?

Stack

Queue

Tree

Linked List

I don’t know