Find Occurrences of an Element in an Array

Medium

Asked by:

5 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⁴

Find Occurrences of an Element in an Array

Medium

Asked by:

5 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⁴

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 is the data type of the elements in the array and the element we are searching for? Are we expecting only integers, or could there be floating-point numbers or other data types?
What should I return if the element is not found in the array? Should I return null, -1, an empty list, or raise an exception?
Can the input array be empty or null? If so, how should I handle those cases?
Are there any constraints on the size of the array? (e.g., can it fit comfortably in memory?)
If the element appears multiple times, should I return the count of occurrences, the indices of all occurrences, or just the first occurrence?

Brute Force Solution

Approach

The most straightforward way to find out how many times a specific thing appears in a collection is to simply look at each thing, one by one. We will check each item to see if it matches what we are looking for. If it does, we count it.

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

Start at the beginning of the collection of items.
Look at the current item.
Is this item the same as the thing we are searching for?
If yes, make a note that we found one more.
Move on to the next item in the collection.
Repeat steps 2-5 until you have looked at every item in the collection.
The number of notes you made is how many times the thing appears.

Code Implementation

def find_occurrences_brute_force(data_series, target_element):
    occurrence_count = 0

    for element_index in range(len(data_series)):

        #Iterate through each element in dataseries
        current_element = data_series[element_index]

        # Compare current element to target
        if current_element == target_element:

            #Increment if both are equal
            occurrence_count += 1

    return occurrence_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the collection of items (array) once. For each of the n items in the collection, it performs a single comparison to check if it matches the target element. Therefore, the number of operations scales linearly with the size of the input array, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm described only uses a single counter variable to keep track of the occurrences. This counter uses a fixed amount of memory irrespective of the input array's size, N. No additional data structures or collections are created. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

To quickly find how many times a specific element appears in a sorted collection, we avoid checking each item individually. Instead, we use a technique similar to looking up a word in a dictionary to rapidly narrow down the possible locations of the element.

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

First, find the very first place where the element shows up in the collection. Use a search method that repeatedly cuts the search area in half to quickly zero in on the location.
Then, find the very last place where the element shows up using the same method of repeatedly halving the search area.
Finally, to get the total count, simply subtract the first location from the last location and add one. This provides the total number of times the element appears without needing to look at everything.

Code Implementation

def find_occurrences(sorted_array, target_element):

    def find_first_occurrence(sorted_array, target_element):
        left_index = 0
        right_index = len(sorted_array) - 1
        first_occurrence = -1

        while left_index <= right_index:
            middle_index = (left_index + right_index) // 2

            if sorted_array[middle_index] == target_element:
                # Found the target, but check for earlier occurrences.
                first_occurrence = middle_index
                right_index = middle_index - 1
            elif sorted_array[middle_index] < target_element:
                left_index = middle_index + 1
            else:
                right_index = middle_index - 1

        return first_occurrence

    def find_last_occurrence(sorted_array, target_element):
        left_index = 0
        right_index = len(sorted_array) - 1
        last_occurrence = -1

        while left_index <= right_index:
            middle_index = (left_index + right_index) // 2

            if sorted_array[middle_index] == target_element:
                # Found the target, check for later occurrences.
                last_occurrence = middle_index
                left_index = middle_index + 1
            elif sorted_array[middle_index] < target_element:
                left_index = middle_index + 1
            else:
                right_index = middle_index - 1

        return last_occurrence

    # Find the index of the first occurrence.
    first_index = find_first_occurrence(sorted_array, target_element)

    # Find the index of the last occurrence.
    last_index = find_last_occurrence(sorted_array, target_element)

    if first_index == -1 or last_index == -1:
        return 0

    # Calculate the number of occurrences.
    number_of_occurrences = last_index - first_index + 1

    return number_of_occurrences

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The algorithm performs two binary searches on the sorted array. Each binary search, to find the first and last occurrences of the target element, has a time complexity of O(log n), where n is the size of the input array. Since we perform two independent binary searches, the overall time complexity is O(log n) + O(log n), which simplifies to O(log n).

Space Complexity

O(1) – The algorithm primarily uses a binary search approach to find the first and last occurrences of the element. This involves storing a few variables to track the start, end, and middle indices during the search process. The number of these variables (like low, high, mid, first occurrence index, last occurrence index) remains constant irrespective of the size of the input array (N). Therefore, the algorithm uses a constant amount of extra space.

Edge Cases

Case	How to Handle
Null or undefined array input	Throw an IllegalArgumentException or return an empty list, depending on the requirements, to avoid NullPointerException.
Empty array input	Return an empty list or an appropriate error code as there are no elements to search.
Array with a single element	Check if the single element matches the search target and return a list containing its index if it does, otherwise return an empty list.
Large array size (memory constraints)	Consider a streaming approach or divide-and-conquer strategy if memory becomes a bottleneck.
Array containing a very large number of occurrences of the target element	The algorithm's performance could degrade if the target element occurs very often, but it should still function correctly with correct time complexity.
Array contains integer overflow values	The element comparison should handle potential overflow errors by either checking for overflow prior to the comparison or using a data type with a larger range.
Target element is null or undefined	Throw an IllegalArgumentException or treat null/undefined as a specific value, depending on the problem constraints.
The array contains NaN (Not a Number) values if the array type is floating point	Handle NaN values appropriately, as NaN != NaN, so a direct comparison would fail; typically, treat them as not equal to the target.