Skip to content

3159. Find Occurrences of an Element in an Array

SourceBiweekly Contest 131 Q2DifficultyMediumRating1262

Description

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

For each queries[i], you need to find 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 answers to all queries.

 

Example 1:

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

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

Explanation:

  • For the 1st query, the first occurrence of 1 is at index 0.
  • For the 2nd query, there are only two occurrences of 1 in nums, so the answer is -1.
  • For the 3rd query, the second occurrence of 1 is at index 2.
  • For the 4th query, there are only two occurrences of 1 in nums, so the answer is -1.

Example 2:

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

Output: [-1]

Explanation:

  • For the 1st query, 5 doesn't exist in nums, so the answer is -1.

 

Constraints:

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

Solutions

Solution 1: Simulation

Thinking

Queries ask for the index of the \(i\)-th occurrence of \(x\). Scanning from the left per query is \(O(nm)\).

All occurrence indices fit in an array \(ids\), after which a query is one lookup.

Collect indices of \(x\), then return \(ids[i-1]\) or \(-1\) when \(i\) is too large.

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.

Next, we traverse the array queries. For each query \(i\), if \(i - 1\) is less than the length of ids, then the answer is ids[i - 1], otherwise, the answer is \(-1\).

The time complexity is \(O(n + m)\), and the space complexity is \(O(n + m)\). Where \(n\) and \(m\) are the lengths of the arrays nums and queries respectively.

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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {
        List<Integer> ids = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == x) {
                ids.add(i);
            }
        }
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = queries[i] - 1;
            ans[i] = j < ids.size() ? ids.get(j) : -1;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> occurrencesOfElement(vector<int>& nums, vector<int>& queries, int x) {
        vector<int> ids;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == x) {
                ids.push_back(i);
            }
        }
        vector<int> ans;
        for (int& i : queries) {
            ans.push_back(i - 1 < ids.size() ? ids[i - 1] : -1);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func occurrencesOfElement(nums []int, queries []int, x int) (ans []int) {
    ids := []int{}
    for i, v := range nums {
        if v == x {
            ids = append(ids, i)
        }
    }
    for _, i := range queries {
        if i-1 < len(ids) {
            ans = append(ans, ids[i-1])
        } else {
            ans = append(ans, -1)
        }
    }
    return
}

1
2
3
4
function occurrencesOfElement(nums: number[], queries: number[], x: number): number[] {
    const ids: number[] = nums.map((v, i) => (v === x ? i : -1)).filter(v => v !== -1);
    return queries.map(i => ids[i - 1] ?? -1);
}

Comments