We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Occurrences of an Element in an Array

Number: 3420

Difficulty: Medium

Paid? No

Companies: Amazon, IBM

Problem Description

Given an integer array nums, an integer array queries, and an integer x, for each query queries[i] you need to determine the index of the queries[i]th occurrence of x in the nums array. If nums contains fewer than queries[i] occurrences of x, return -1 for that query.

Key Insights

  • Pre-process the nums array to record the positions (indices) where the element x appears.
  • For each query, check if the occurrence number requested is within the bounds of the precomputed list.
  • Return the corresponding index if available; otherwise, return -1.

Space and Time Complexity

Time Complexity: O(n + q) where n is the length of nums (to precompute positions) and q is the length of queries (to answer each query in constant time). Space Complexity: O(n) in the worst case where all elements in nums equal x and are stored in the positions array.

Solution

The solution involves a two-step approach:

  1. Iterate through the nums array once to store the index of each occurrence of x in a list called positions.
  2. For each query in queries, check if there is at least as many occurrences as the query specifies by verifying if queries[i] is less than or equal to the length of positions. If yes, return the (queries[i]-1)th element from positions (since it is zero-indexed). Otherwise, return -1.

This approach efficiently handles multiple queries by utilizing precomputed data and simple indexing.

Code Solutions

# Function to find occurrences of x at specified query indices
def find_occurrences(nums, queries, x):
    # Precompute the indices where x occurs in nums
    positions = []
    for index, num in enumerate(nums):
        if num == x:
            positions.append(index)
    
    # Process each query
    results = []
    for occurrence in queries:
        # Check if the requested occurrence exists
        if occurrence <= len(positions):
            results.append(positions[occurrence - 1])  # Convert to zero-based index
        else:
            results.append(-1)
    return results

# Example usage:
nums = [1, 3, 1, 7]
queries = [1, 3, 2, 4]
x = 1
print(find_occurrences(nums, queries, x))  # Output: [0, -1, 2, -1]
← Back to All Questions