Intersection of Two Arrays

Finding the intersection of two arrays - i.e. the common elements between two lists - is a real-world task you’ll do when reconciling user preferences, matching tags across datasets, or merging log sources. In an interview, it tests your ability to move from a naive pairwise comparison to more efficient set- or sort-based techniques.

Problem Statement

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.

// Signature presented in a technical interview
public int[] intersection(int[] nums1, int[] nums2);

1. Clarify Requirements Before Jumping Into Code

I want to confirm exactly what the interviewer expects:

• Should the result contain unique values or duplicates? Unique only.

• Does the order of the result matter? Any order is fine.

• What are typical sizes of the arrays? Can be large, so aim for better than O(n·m).

• Are the arrays sorted? No guarantee.

• What space/time constraints are we targeting? Ideally O(n + m) time, O(min(n,m)) extra space.

2. Identify the Category of the Question

This is a set-intersection problem on unsorted arrays. It falls into the hashing or two-pointer on sorted arrays categories. Recognizing “find common unique elements” suggests using a set or sorting then scanning.

3. Consider a Brute-Force Approach to Understand the Problem

The simplest idea is two nested loops:

for each x in nums1:
  for each y in nums2:
    if x == y and x not yet in result:
      add x to result

Time complexity is O(n·m), plus extra checks to avoid duplicates. That will time out on large inputs but confirms correctness.

4. Brainstorm More Solutions

To optimize, I consider these:

• Hash Set Approach: Insert all elements of the smaller array into a set. Then iterate the larger array, collecting matches into a result set. This runs in O(n + m) time, uses O(min(n,m)) extra space, and naturally enforces uniqueness.

• Sorting + Two-Pointer: Sort both arrays in O(n log n + m log m) time, then use two pointers to scan in O(n + m), collecting matches. This uses O(1) extra space if sorting in-place, but costs the sorting overhead.

• Binary Search: Sort one array, then for each element in the other perform binary search in O(log n) each, yielding O(m log n) time.

• Bitset or Boolean Array: If values are bounded within a known small range, use a boolean array for presence, but integers may not be limited.

I want O(n + m) time and minimal extra memory, so the hash set approach feels optimal. To arrive at it in real time, I’d think: I need O(1) lookups to avoid nested loops, and a set gives me that. Uniqueness is handled by the set itself.

5. Discuss Trade-Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Brute-Force	O(n·m)	O(1)	Very simple	Too slow for large arrays
Hash Set	O(n + m)	O(min(n,m))	Fast, unique enforced, simple to code	Extra memory for sets
Sorting + Two-Pointer	O(n log n + m log m)	O(1)–O(n+m)	No extra data structures (in-place)	Sorting overhead, more complex logic
Binary Search	O(m log n)	O(1)	Good if one array much smaller	Log factor and repeated searches

The hash set solution meets both time and simplicity goals.

6. Write Pseudocode to Structure Your Thoughts

function intersection(nums1, nums2):
  if length(nums1) > length(nums2):
    swap(nums1, nums2)

  set1 = empty set
  for x in nums1:
    add x to set1

  resultSet = empty set
  for y in nums2:
    if y in set1:
      add y to resultSet

  return array converted from resultSet

7. Consider Edge Cases

• One or both arrays empty → returns empty array

• No common elements → returns empty array

• All elements identical in both → returns single element

• Large arrays with few overlaps → performance check

• Negative numbers or zeros → handled normally by the set

8. Write Full Code Syntax

import java.util.*;

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array for space efficiency
        if (nums1.length > nums2.length) {
            return intersection(nums2, nums1);
        }

        Set<Integer> set1 = new HashSet<>();
        for (int x : nums1) {
            set1.add(x);
        }

        Set<Integer> resultSet = new HashSet<>();
        for (int y : nums2) {
            if (set1.contains(y)) {
                resultSet.add(y);
            }
        }

        int[] result = new int[resultSet.size()];
        int i = 0;
        for (int val : resultSet) {
            result[i++] = val;
        }
        return result;
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();

    System.out.println(Arrays.toString(
        sol.intersection(new int[]{1,2,2,1}, new int[]{2,2})
    ));  // [2]

    System.out.println(Arrays.toString(
        sol.intersection(new int[]{4,9,5}, new int[]{9,4,9,8,4})
    ));  // [9,4] or [4,9] in any order

    System.out.println(Arrays.toString(
        sol.intersection(new int[]{}, new int[]{1,2,3})
    ));  // []

    System.out.println(Arrays.toString(
        sol.intersection(new int[]{1,2,3}, new int[]{})
    ));  // []

    System.out.println(Arrays.toString(
        sol.intersection(new int[]{5,5,5}, new int[]{5})
    ));  // [5]
}

10. Key Lessons to Remember for Future Questions

• When you need unique intersections, a hash set naturally enforces uniqueness and offers O(1) lookups.

• Sorting plus two-pointer is a solid fallback when extra memory is restricted but costs O(n log n).

Good Luck and Happy Coding!