Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Examples

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Explanation: The intersection contains only the element 2.

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4] or [4,9]
Explanation: The intersection contains elements 9 and 4. Order does not matter.

Constraints

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

Thinking Process

  1. Hash Set for Uniqueness: Automatically handles duplicates
  • Two indices move toward each other or in the same direction.
  • Works on sorted arrays or when in-place modification is required.
  • Loop invariant: all indices outside [left, right] are already resolved.
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Opposite ends (this problem) O(n) O(1) Sorted array pair search, reversal
Slow / fast pointers O(n) O(1) Linked list middle, cycle detection
Same-direction chase O(n) O(1) Remove duplicates in-place
Sliding window (variable) O(n) O(1) Subarray with constraint

Solution

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> seen(nums1.begin(), nums1.end());
        vector<int> rtn;
        for(int num: nums2) {
            if(seen.contains(num)) {
                rtn.emplace_back(num);
                seen.erase(num);
            }
        }
        return rtn;
    }
};

Solution Explanation

Approach: Opposite ends (this problem)

Key idea: 1. Hash Set for Uniqueness: Automatically handles duplicates

How the code works:

  1. Hash Set for Uniqueness: Automatically handles duplicates
    • Two indices move toward each other or in the same direction.
    • Works on sorted arrays or when in-place modification is required.
    • Loop invariant: all indices outside [left, right] are already resolved.

Walkthrough — input nums1 = [1,2,2,1], nums2 = [2,2], expected output [2]:

The intersection contains only the element 2.

Common Mistakes

  1. No intersection: nums1 = [1,2,3], nums2 = [4,5,6] → []
  2. Complete overlap: nums1 = [1,2,3], nums2 = [1,2,3] → [1,2,3]
  3. One array empty: nums1 = [], nums2 = [1,2] → []
  4. Duplicates in both: nums1 = [1,1,2,2], nums2 = [2,2] → [2]

  5. Single element: nums1 = [1], nums2 = [1] → [1]

  6. Not removing from set: Results in duplicate elements in output
  7. Using vector instead of set: Doesn’t handle duplicates in nums1
  8. Wrong comparison: Comparing entire arrays instead of elements
  9. Forgetting empty check: Not handling empty arrays
  10. Order dependency: Trying to maintain order when not needed

Key Takeaways

  1. Hash Set for Uniqueness: Automatically handles duplicates
  2. Erase After Add: Prevents duplicate results efficiently
  3. Order Independence: Can return result in any order
  4. Space-Time Trade-off: Hash set uses more space but provides O(1) lookup

References

Template Reference