Jobs

Interviews

Discussions

Find Occurrences of an Element in an Array

Medium

Asked by:

23 views

Topics:

Arrays

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 1^st query, the first occurrence of 1 is at index 0.
For the 2^nd query, there are only two occurrences of 1 in nums, so the answer is -1.
For the 3^rd query, the second occurrence of 1 is at index 2.
For the 4^th 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 1^st query, 5 doesn't exist in nums, so the answer is -1.

Constraints:

1 <= nums.length, queries.length <= 10⁵
1 <= queries[i] <= 10⁵
1 <= nums[i], x <= 10⁴

Try coding it in LeetCode

Find Occurrences of an Element in an Array

Medium

Asked by:

23 views

Topics:

Arrays

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

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 1^st query, the first occurrence of 1 is at index 0.
For the 2^nd query, there are only two occurrences of 1 in nums, so the answer is -1.
For the 3^rd query, the second occurrence of 1 is at index 2.
For the 4^th 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 1^st query, 5 doesn't exist in nums, so the answer is -1.

Constraints:

1 <= nums.length, queries.length <= 10⁵
1 <= queries[i] <= 10⁵
1 <= nums[i], x <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `nums` array and the `queries` array? For instance, can they be very large, suggesting that a pre-processing step might be beneficial?
What is the range of values for the elements in `nums`, `value`, and `queries`? Can they be negative, zero, or very large numbers?
The problem refers to the 'specific occurrence' of a value. Are the occurrences 1-indexed or 0-indexed? For example, does a query for the 1st occurrence mean the very first time the value appears?
What should be the expected behavior if the `nums` array or the `queries` array is empty?
Is it possible for the `queries` array to contain non-positive numbers, like 0 or negative integers? If so, how should those be handled?

Brute Force Solution

Approach

The simplest way to solve this is to look at every single item in the collection one by one. We'll keep a running count of how many times we've seen the special number we're looking for, and stop as soon as our count matches the specific occurrence we want.

Here's how the algorithm would work step-by-step:

First, we need to find all the places where the special number appears in our list of items.
Go through the entire list of items from the very beginning to the very end.
Each time you encounter the special number you're looking for, make a note of its position.
After checking every item, you will have a new list containing only the positions where the special number was found.
Now, look at this new list of positions.
If the occurrence you want is within the bounds of this new list (for example, if you want the 3rd occurrence and you found it at least 3 times), simply pick the position from that spot in the list.
If the occurrence you want is not in the list (for example, you wanted the 5th occurrence but only found it 2 times), it means the number didn't appear that many times.

Code Implementation

from typing import List

def occurrencesOfElement(nums: List[int], queries: List[int], target_number: int) -> List[int]:
    indices_of_target = []

    # First, collect all indices where the target number appears in the original list.
    for index, current_number in enumerate(nums):
        if current_number == target_number:
            indices_of_target.append(index)

    results = []
    for occurrence_query in queries:
        # The query is 1-based, so we must adjust it to access our 0-based list of indices.
        index_in_indices_list = occurrence_query - 1

        # Check if the requested occurrence is valid (i.e., we found the target that many times).
        if 0 <= index_in_indices_list < len(indices_of_target):
            results.append(indices_of_target[index_in_indices_list])
        else:
            # If the requested occurrence doesn't exist, the problem specifies we should use -1.
            results.append(-1)

    return results

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the need to iterate through the entire input array to find all occurrences of the target element. This single pass inspects each of the n elements in the array once. Storing the indices and later accessing the k-th index from the new list are constant time operations on average, but the initial search dominates the runtime. Therefore, the total number of operations is directly proportional to the size of the input array, n, which simplifies to O(n).

Space Complexity

O(N) – The plain English explanation describes creating a new list to store the positions (indices) of every occurrence of the target number. In the worst-case scenario, the input array, with a size of N, could be filled entirely with the target number. This would result in the auxiliary list of positions also growing to a size of N, leading to space complexity that is linearly proportional to the size of the input array.

Optimal Solution

Approach

The best way to solve this is to prepare ahead of time by finding all the locations of the special number first. Once we have a list of all these locations, we can quickly look up the answer for any requested occurrence without having to search the entire original collection again.

Here's how the algorithm would work step-by-step:

First, go through the original collection of numbers from beginning to end.
Every time you see the special number you're looking for, make a note of its position.
Collect all of these noted positions into a new, separate list. This new list now exclusively contains the locations of every instance of the special number, in the order they appeared.
Now, look at the list of requested occurrences.
For each requested occurrence number, like the 1st, 3rd, or 5th, use it to directly find the corresponding position in your new list of locations.
If a requested occurrence is too large (for example, asking for the 10th occurrence when there are only 5), it means that occurrence doesn't exist, so we should note that it's not possible.
Finally, gather all the positions you found (or the 'not possible' notes) and present them as the final answer.

Code Implementation

def find_occurrences(numbers_collection, target_number, occurrence_queries):
    # Pre-calculate and store all indices where the target number appears.
    locations_of_target = []
    for index, current_number in enumerate(numbers_collection):
        if current_number == target_number:
            locations_of_target.append(index)

    query_answers = []
    # Process each requested occurrence to find its corresponding index.
    for requested_occurrence in occurrence_queries:
        # The requested occurrence is 1-based, so we must adjust it for 0-based list access.
        query_index = requested_occurrence - 1

        # Check if the requested occurrence is valid within the bounds of our found locations.
        if 0 <= query_index < len(locations_of_target):
            query_answers.append(locations_of_target[query_index])
        else:
            query_answers.append(-1)

    return query_answers

Big(O) Analysis

Time Complexity

O(N + Q) – The time complexity is determined by two main, independent operations. First, we iterate through the entire input array of size N once to find all occurrences of the special number and store their indices, which takes O(N) time. Second, we process each of the Q queries by performing a simple lookup in the precomputed list of indices, which takes O(1) for each query, totaling O(Q). Since these two steps happen sequentially, not nested within each other, the total time complexity is the sum of their costs, which simplifies to O(N + Q).

Space Complexity

O(K + Q) – The primary auxiliary space is used to store the locations of the special number. In the worst-case scenario, where every number in the input array `nums` is the target element `x`, this list of locations could grow to the same size as `nums`, which we can denote as K. Additionally, we need to create a result list to store the answers for each of the `queries`, which has a size Q. Therefore, the total auxiliary space is proportional to the number of occurrences plus the number of queries.

Edge Cases

Case	How to Handle
The `nums` array is empty or null	The preprocessing step will result in an empty map of occurrences, leading to -1 for all queries.
The `queries` array is empty or null	The solution should return an empty array as there are no queries to process.
The target `value` does not exist in the `nums` array	The map of occurrences for `value` will be empty, causing all queries to correctly return -1.
A query asks for the k-th occurrence, but `value` appears fewer than k times	The solution will correctly return -1 as the requested 1-based index k will be out of bounds for the stored list of occurrences.
A query value is zero or negative (e.g., query for the 0th or -1st occurrence)	The solution should handle this gracefully by returning -1, as queries are 1-based.
The `nums` array contains all identical elements matching the `value`	The map will store a single entry with a long list of indices, which is an efficient way to handle this case.
Large inputs for `nums` and `queries` (e.g., up to 10^5 elements each)	A preprocessing approach with a hash map ensures each query is answered in constant time, scaling efficiently for large inputs.
Inputs contain negative numbers or zeros for `nums` elements and the `value`	Using a hash map works correctly with any integer values, including negatives and zero, without special logic.

The `nums` array is empty or null

How to Handle:

The preprocessing step will result in an empty map of occurrences, leading to -1 for all queries.

The `queries` array is empty or null

How to Handle:

The solution should return an empty array as there are no queries to process.

The target `value` does not exist in the `nums` array

How to Handle:

The map of occurrences for `value` will be empty, causing all queries to correctly return -1.

A query asks for the k-th occurrence, but `value` appears fewer than k times

How to Handle:

The solution will correctly return -1 as the requested 1-based index k will be out of bounds for the stored list of occurrences.

A query value is zero or negative (e.g., query for the 0th or -1st occurrence)

How to Handle:

The solution should handle this gracefully by returning -1, as queries are 1-based.

The `nums` array contains all identical elements matching the `value`

How to Handle:

The map will store a single entry with a long list of indices, which is an efficient way to handle this case.

Large inputs for `nums` and `queries` (e.g., up to 10^5 elements each)

How to Handle:

A preprocessing approach with a hash map ensures each query is answered in constant time, scaling efficiently for large inputs.

Inputs contain negative numbers or zeros for `nums` elements and the `value`

How to Handle:

Using a hash map works correctly with any integer values, including negatives and zero, without special logic.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `nums` array and the `queries` array? For instance, can they be very large, suggesting that a pre-processing step might be beneficial?
What is the range of values for the elements in `nums`, `value`, and `queries`? Can they be negative, zero, or very large numbers?
The problem refers to the 'specific occurrence' of a value. Are the occurrences 1-indexed or 0-indexed? For example, does a query for the 1st occurrence mean the very first time the value appears?
What should be the expected behavior if the `nums` array or the `queries` array is empty?
Is it possible for the `queries` array to contain non-positive numbers, like 0 or negative integers? If so, how should those be handled?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, we need to find all the places where the special number appears in our list of items.
Go through the entire list of items from the very beginning to the very end.
Each time you encounter the special number you're looking for, make a note of its position.
After checking every item, you will have a new list containing only the positions where the special number was found.
Now, look at this new list of positions.
If the occurrence you want is within the bounds of this new list (for example, if you want the 3rd occurrence and you found it at least 3 times), simply pick the position from that spot in the list.
If the occurrence you want is not in the list (for example, you wanted the 5th occurrence but only found it 2 times), it means the number didn't appear that many times.

Code Implementation

from typing import List

def occurrencesOfElement(nums: List[int], queries: List[int], target_number: int) -> List[int]:
    indices_of_target = []

    # First, collect all indices where the target number appears in the original list.
    for index, current_number in enumerate(nums):
        if current_number == target_number:
            indices_of_target.append(index)

    results = []
    for occurrence_query in queries:
        # The query is 1-based, so we must adjust it to access our 0-based list of indices.
        index_in_indices_list = occurrence_query - 1

        # Check if the requested occurrence is valid (i.e., we found the target that many times).
        if 0 <= index_in_indices_list < len(indices_of_target):
            results.append(indices_of_target[index_in_indices_list])
        else:
            # If the requested occurrence doesn't exist, the problem specifies we should use -1.
            results.append(-1)

    return results

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, go through the original collection of numbers from beginning to end.
Every time you see the special number you're looking for, make a note of its position.
Collect all of these noted positions into a new, separate list. This new list now exclusively contains the locations of every instance of the special number, in the order they appeared.
Now, look at the list of requested occurrences.
For each requested occurrence number, like the 1st, 3rd, or 5th, use it to directly find the corresponding position in your new list of locations.
If a requested occurrence is too large (for example, asking for the 10th occurrence when there are only 5), it means that occurrence doesn't exist, so we should note that it's not possible.
Finally, gather all the positions you found (or the 'not possible' notes) and present them as the final answer.

Code Implementation

def find_occurrences(numbers_collection, target_number, occurrence_queries):
    # Pre-calculate and store all indices where the target number appears.
    locations_of_target = []
    for index, current_number in enumerate(numbers_collection):
        if current_number == target_number:
            locations_of_target.append(index)

    query_answers = []
    # Process each requested occurrence to find its corresponding index.
    for requested_occurrence in occurrence_queries:
        # The requested occurrence is 1-based, so we must adjust it for 0-based list access.
        query_index = requested_occurrence - 1

        # Check if the requested occurrence is valid within the bounds of our found locations.
        if 0 <= query_index < len(locations_of_target):
            query_answers.append(locations_of_target[query_index])
        else:
            query_answers.append(-1)

    return query_answers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
The `nums` array is empty or null	The preprocessing step will result in an empty map of occurrences, leading to -1 for all queries.
The `queries` array is empty or null	The solution should return an empty array as there are no queries to process.
The target `value` does not exist in the `nums` array	The map of occurrences for `value` will be empty, causing all queries to correctly return -1.
A query asks for the k-th occurrence, but `value` appears fewer than k times	The solution will correctly return -1 as the requested 1-based index k will be out of bounds for the stored list of occurrences.
A query value is zero or negative (e.g., query for the 0th or -1st occurrence)	The solution should handle this gracefully by returning -1, as queries are 1-based.
The `nums` array contains all identical elements matching the `value`	The map will store a single entry with a long list of indices, which is an efficient way to handle this case.
Large inputs for `nums` and `queries` (e.g., up to 10^5 elements each)	A preprocessing approach with a hash map ensures each query is answered in constant time, scaling efficiently for large inputs.
Inputs contain negative numbers or zeros for `nums` elements and the `value`	Using a hash map works correctly with any integer values, including negatives and zero, without special logic.

The `nums` array is empty or null

How to Handle:

The preprocessing step will result in an empty map of occurrences, leading to -1 for all queries.

The `queries` array is empty or null

How to Handle:

The solution should return an empty array as there are no queries to process.

The target `value` does not exist in the `nums` array

How to Handle:

The map of occurrences for `value` will be empty, causing all queries to correctly return -1.

A query asks for the k-th occurrence, but `value` appears fewer than k times

How to Handle:

The solution will correctly return -1 as the requested 1-based index k will be out of bounds for the stored list of occurrences.

A query value is zero or negative (e.g., query for the 0th or -1st occurrence)

How to Handle:

The solution should handle this gracefully by returning -1, as queries are 1-based.

The `nums` array contains all identical elements matching the `value`

How to Handle:

The map will store a single entry with a long list of indices, which is an efficient way to handle this case.

Large inputs for `nums` and `queries` (e.g., up to 10^5 elements each)

How to Handle:

A preprocessing approach with a hash map ensures each query is answered in constant time, scaling efficiently for large inputs.

Inputs contain negative numbers or zeros for `nums` elements and the `value`

How to Handle:

Using a hash map works correctly with any integer values, including negatives and zero, without special logic.