How to Solve Intersection of Two Arrays

To solve the "Intersection of Two Arrays" problem, use an array scanning approach combined with hash lookup to efficiently find unique common elements. This approach leverages hash tables to track elements and ensures the output only contains unique elements, avoiding duplicates even when arrays have repetitions. The solution's time complexity is linear, making it efficient for larger inputs.

Problem Statement

You are given two integer arrays, nums1 and nums2. Your task is to return an array containing the intersection of the two arrays, where each element is unique. The order of elements in the result does not matter, but duplicates should be eliminated in the final output.

For example, given nums1 = [1,2,2,1] and nums2 = [2,2], the correct result is [2]. Elements may appear multiple times in the input arrays, but the output should only contain the unique common elements.

Examples

Example 1

Input: nums1 = [1,2,2,1], nums2 = [2,2]

Output: [2]

Example details omitted.

Example 2

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

Output: [9,4]

[4,9] is also accepted.

Constraints

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

Solution Approach

Array Scanning and Hash Table Lookup

Scan through one of the arrays (nums1), adding each element to a hash table. Then, iterate through the second array (nums2) and check if the element exists in the hash table. This allows for quick lookups to find common elements, ensuring uniqueness by adding only elements found in both arrays.

Using Set for Uniqueness

Use a set to store the common elements found during the array scanning. Since sets automatically handle uniqueness, they are ideal for ensuring that only distinct elements are included in the final result, regardless of duplicates in the original arrays.

Optimized Space and Time Complexity

The time complexity of this approach is O(n + m), where n and m are the lengths of nums1 and nums2 respectively. The space complexity is O(n) due to the storage required for the hash table or set. This makes the solution efficient for inputs with large arrays.

Complexity Analysis

The time complexity is O(n + m) because we perform one pass through nums1 and nums2. The space complexity is O(n) due to the need to store unique elements from nums1 in a hash table or set, which depends on the size of the first array.

What Interviewers Usually Probe

• A successful solution will efficiently scan through both arrays and utilize a hash table or set for fast lookups.
• The candidate should avoid unnecessary sorting or complex operations, focusing instead on the linear scan and hash table approach.
• Watch for the candidate using inefficient solutions that don't ensure uniqueness or have higher time complexity than O(n + m).

Common Pitfalls or Variants

Common pitfalls

• Failing to remove duplicates from the result, leading to incorrect output.
• Using an inefficient solution with a higher time complexity, such as sorting the arrays, which would make the solution O(n log n).
• Not utilizing hash tables or sets to efficiently check for intersections and uniqueness.

Follow-up variants

• What if the arrays are already sorted? In this case, the two-pointer technique could be used to find intersections more efficiently.
• What if the arrays contain only unique elements? The problem becomes simpler as you only need to find the intersection without needing to handle duplicates.
• How would this solution change if the arrays were much larger? You could explore further optimizations or techniques, but the hash lookup method will still be efficient.

How GhostInterview Helps

• GhostInterview helps you quickly apply the array scanning and hash lookup pattern to this problem, ensuring efficient solution development.
• By providing structured problem-solving guidance, GhostInterview aids in recognizing key failure modes, such as inefficient solutions or failure to eliminate duplicates.
• With insights into common pitfalls and a focus on the exact solution approach, GhostInterview ensures that your solution is optimal and well-executed during the interview.

Topic Pages

• Array
• Hash Table
• Two Pointers
• Binary Search
• Sorting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the primary pattern for solving the Intersection of Two Arrays problem?

The primary pattern is array scanning combined with hash lookup, ensuring efficient identification of common elements while maintaining uniqueness.

How can I ensure my solution handles duplicates correctly?

Using a hash table or set will automatically remove duplicates, ensuring that each common element appears only once in the result.

Can this problem be solved with sorting?

While sorting could be used, it would increase the time complexity to O(n log n). The optimal approach is to use hash lookups for a linear-time solution.

What if I need to handle arrays of different sizes?

The solution still works efficiently regardless of the array sizes, as long as you use the linear scan and hash lookup approach.

What is the best way to handle larger inputs?

For larger inputs, maintaining the O(n + m) time complexity with hash lookups ensures optimal performance, as opposed to using slower methods like sorting.