algoadvance

You are given two integer arrays arr1 and arr2. Your task is to find all the elements that are common between the two arrays. Both the arrays can contain duplicates, but you should return each common element only once. The result can be returned in any order.

Example:

arr1 = [1, 2, 2, 1]
arr2 = [2, 2]
Output: [2]

arr1 = [4, 9, 5]
arr2 = [9, 4, 9, 8, 4]
Output: [9, 4]

Clarifying Questions

1. Q: What should be returned if there are no common elements? A: Return an empty list.
2. Q: Can the input arrays be empty? A: Yes, the arrays can be empty. If both or one of the arrays is empty, the result should be an empty list.
3. Q: How should the results be ordered? A: The order of the result does not matter.

Strategy

To solve the problem, we can use a two-step approach:

1. Convert the arrays to sets which inherently handle duplicate elements.
2. Compute the intersection of the two sets, which gives us the common elements without duplicates.

Steps:

1. Convert arr1 to a set called set1.
2. Convert arr2 to a set called set2.
3. Find the intersection of set1 and set2.
4. Convert the result back to a list and return.

Time Complexity

• Converting a list to a set takes O(n) time, where n is the length of the list.
• Finding the intersection of two sets each of size n and m respectively takes O(min(n, m)) time.
• Thus, the overall time complexity of this approach is O(n + m), where n and m are the lengths of the two input arrays.

Code

def find_common_elements(arr1, arr2):
    # Convert arrays to sets
    set1 = set(arr1)
    set2 = set(arr2)
    
    # Find the intersection of both sets
    common_elements = set1.intersection(set2)
    
    # Convert the result back to a list
    return list(common_elements)

# Example usage
arr1 = [1, 2, 2, 1]
arr2 = [2, 2]
print(find_common_elements(arr1, arr2))  # Output: [2]

arr1 = [4, 9, 5]
arr2 = [9, 4, 9, 8, 4]
print(find_common_elements(arr1, arr2))  # Output: [9, 4]

This code correctly finds the common elements between two arrays, ensures no duplicates in the result, and handles empty inputs gracefully.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?