Intersection of Two Arrays - Video Solutions

Problem Overview: You receive two integer arrays and must return their intersection. The result should contain only unique values that appear in both arrays, and the order does not matter.

Approach 1: Using Hash Sets (O(m + n) time, O(m + n) space)

This is the most direct solution. Insert all elements of the first array into a hash set, then iterate through the second array and check whether each value exists in the set. If the lookup succeeds, add it to a result set to ensure uniqueness. Hash lookups run in average O(1) time, so the overall complexity becomes linear relative to the total number of elements. This approach works well for unsorted inputs and demonstrates practical use of a hash table to eliminate duplicates efficiently.

The key insight is that sets automatically handle uniqueness. Instead of manually checking whether a value was already added, the set structure guarantees that duplicates are ignored. In interviews, this approach is usually the first optimized solution candidates present because it is easy to reason about and scales well for large arrays.

Approach 2: Sorting and Two Pointers (O(m log m + n log n) time, O(1) extra space)

If modifying the arrays is allowed, sorting both arrays enables a pointer-based scan. First sort the arrays using any efficient sorting algorithm. Then place one pointer at the start of each array and move them forward depending on the comparison of the current values. When the numbers match, add the value to the result and advance both pointers while skipping duplicates.

This approach relies on the idea that once arrays are sorted, equal elements align naturally during a linear scan. The two pointers technique avoids nested loops and reduces comparison overhead. The total runtime is dominated by the sorting step, which is O(m log m + n log n). The scan itself runs in O(m + n). This technique is common in problems involving sorted arrays and belongs to the broader family of sorting-based optimizations.

Recommended for interviews: The hash set solution is typically expected because it achieves optimal O(m + n) time and is easy to implement in languages like Python, Java, or C++. The sorting + two pointers method is still valuable to discuss. It shows you understand alternative strategies and how pointer techniques reduce comparisons when working with ordered data.