algoadvance

Leetcode 2956. Find Common Elements Between Two Arrays

Problem Statement

Given two integer arrays nums1 and nums2, write a function findCommonElements that returns an array containing the common elements between the two arrays. Each element in the result array must be unique.

Clarifying Questions

1. Input Size: What is the maximum size of the input arrays?
   • Assume there is no explicit constraint on size, but they can be quite large (up to millions of elements).
2. Order of Output: Does the order of the common elements in the output array matter?
   • No, the order of elements in the output array does not matter.
3. Duplicates: Should duplicates in the input arrays be considered more than once in the output?
   • No, the result should contain unique common elements only.
4. Types of Elements: Can the input arrays contain negative numbers?
   • Yes, the input arrays can contain any integers including negative numbers.

Strategy

1. Set Operations:
   • Utilize sets to find common elements since sets inherently manage uniqueness and provide efficient operations.
   • Convert each array into a set to remove duplicates within the same array.
   • Use set intersection to determine common elements between the two sets.
2. Steps:
   • Convert both arrays into sets.
   • Use the intersection operation to find common elements between the two sets.
   • Convert the resulting set back into an array and return it.

Code

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int[] findCommonElements(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();

        // Convert first array to a set
        for (int num : nums1) {
            set1.add(num);
        }

        // Convert second array to a set
        for (int num : nums2) {
            set2.add(num);
        }

        // Find the intersection of the two sets
        set1.retainAll(set2);

        // Convert the result set to an array
        int[] result = new int[set1.size()];
        int index = 0;
        for (int num : set1) {
            result[index++] = num;
        }

        return result;
    }
}

Time Complexity

• Construction of Sets: O(n + m) where n is the length of nums1 and m is the length of nums2.
• Intersection Operation: O(min(n, m)) on average for set intersection.
• Total Complexity: O(n + m), since constructing the sets and performing the intersection are linear in the size of the input arrays.

Space Complexity

• Space for Sets: O(n + m) to store elements from both arrays.
• Result Space: O(min(n, m)) for the resultant array holding common elements.
• Total Space: O(n + m) due to the sets used to hold elements from both arrays.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?