Find Occurrences of an Element in an Array

Medium
1818.

Find Occurrences of an Element in an Array

Find Occurrences of an Element in an Array is a medium coding problem on arrays and hash table, asked in Amazon interviews.

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

For each queries[i], find the index of the queries[i]-th occurrence of x in nums (counting occurrences from 1, left to right). If x occurs fewer than queries[i] times, the answer is -1.

Return an array answer with the answers to all the queries, in order.

Example 1

Input
nums = [1,3,1,7], queries = [1,3,2,4], x = 1
Output
[0,-1,2,-1]
Explanation
1 occurs at indices 0 and 2, so the 1st occurrence is at 0, the 2nd at 2, and there is no 3rd or 4th.

Example 2

Input
nums = [1,2,3], queries = [10], x = 5
Output
[-1]
Explanation
5 never occurs.

Example 3

Input
nums = [4,4,4], queries = [3,1,2,3], x = 4
Output
[2,0,1,2]

Constraints

  • 1 <= nums.length, queries.length <= 10^5
  • 1 <= queries[i] <= 10^5
  • 1 <= nums[i], x <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[]} queries
 * @param {number} x
 * @return {number[]}
 */
var occurrencesOfElement = function(nums, queries, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Occurrences of an Element in an Array — Solution

Find Occurrences of an Element in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find Occurrences of an Element in an Array is a medium coding problem on arrays and hash table, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

For each queries[i], find the index of the queries[i]-th occurrence of x in nums (counting occurrences from 1, left to right). If x occurs fewer than queries[i] times, the answer is -1.

Return an array answer with the answers to all the queries, in order.

Example 1

Input: nums = [1,3,1,7], queries = [1,3,2,4], x = 1
Output: [0,-1,2,-1]
Explanation: 1 occurs at indices 0 and 2, so the 1st occurrence is at 0, the 2nd at 2, and there is no 3rd or 4th.

Example 2

Input: nums = [1,2,3], queries = [10], x = 5
Output: [-1]
Explanation: 5 never occurs.

Example 3

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

Constraints

  • 1 <= nums.length, queries.length <= 10^5
  • 1 <= queries[i] <= 10^5
  • 1 <= nums[i], x <= 10^4

Hints for Find Occurrences of an Element in an Array

  1. Hint 1

    Scanning nums once per query is too slow for 10^5 queries.

  2. Hint 2

    Collect, in one pass, the list of indices where nums[i] == x, in increasing order.

  3. Hint 3

    The q-th occurrence is then simply element q - 1 of that list, if the list is long enough.

How to solve Find Occurrences of an Element in an Array

Precompute the positions of x in order; every query is then an array lookup.

Approach

  1. Scan nums and append every index i with nums[i] == x to a list pos.
  2. For each query q, answer pos[q - 1] if q <= pos.length, otherwise -1.

Why it works

pos lists the occurrences of x left to right, so its (q - 1)-th entry (0-based) is by definition the q-th occurrence; a shorter list means there are fewer than q occurrences.

Complexity

  • Time — O(n + q)
  • Space — O(n)

Pitfalls

  • Queries are 1-based: the 1st occurrence is pos[0].
  • Queries can be far larger than the number of occurrences — check the bound before indexing.

Reference solution

Python

from typing import List

def occurrencesOfElement(nums: List[int], queries: List[int], x: int) -> List[int]:
    pos = [i for i, v in enumerate(nums) if v == x]
    return [pos[q - 1] if q <= len(pos) else -1 for q in queries]

Java

public static int[] occurrencesOfElement(int[] nums, int[] queries, int x) {
    int[] pos = new int[nums.length];
    int k = 0;
    for (int i = 0; i < nums.length; i++) if (nums[i] == x) pos[k++] = i;
    int[] out = new int[queries.length];
    for (int j = 0; j < queries.length; j++) out[j] = queries[j] <= k ? pos[queries[j] - 1] : -1;
    return out;
}

C++

vector<int> occurrencesOfElement(vector<int>& nums, vector<int>& queries, int x) {
    vector<int> pos;
    for (int i = 0; i < (int) nums.size(); i++) if (nums[i] == x) pos.push_back(i);
    vector<int> out;
    out.reserve(queries.size());
    for (int q : queries) out.push_back(q <= (int) pos.size() ? pos[q - 1] : -1);
    return out;
}

JavaScript

var occurrencesOfElement = function(nums, queries, x) {
    var pos = [];
    for (var i = 0; i < nums.length; i++) if (nums[i] === x) pos.push(i);
    var out = [];
    for (var j = 0; j < queries.length; j++) out.push(queries[j] <= pos.length ? pos[queries[j] - 1] : -1);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets