Two Pointers — Intersection of Two Arrays II

↗ LeetCode: Intersection of Two Arrays II · Easy · pattern chapter →

Asked atMetaAmazonGoogleUber

Return the multi-set intersection (each element appears min(cnt_a, cnt_b) times).

Example 1 — nums1=[1,2,2,1], nums2=[2,2] → [2,2]Example 2 — nums1=[4,9,5], nums2=[9,4,9,8,4] → [4,9] or [9,4]

Constraints — 1 ≤ n, m ≤ 1000. Brute nested-loop is O(n·m) = 10⁶ ops at n,m=10³. HashMap of counts is O(n+m) = 2·10³ ops, generalises to streaming inputs of 10⁹ elements.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Hash-map count

Count nums1; iterate nums2 decrementing. O(n+m).

Approach 2 — Sort + two-pointer (canonical for pre-sorted)

Insight. After sorting, walk both arrays; on equal emit and advance both.

int[] intersect(int[] nums1, int[] nums2) {
    Arrays.sort(nums1); Arrays.sort(nums2);
    List<Integer> out = new ArrayList<>();
    int i = 0, j = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] == nums2[j]) { out.add(nums1[i]); i++; j++; }
        else if (nums1[i] < nums2[j]) i++;
        else j++;
    }
    return out.stream().mapToInt(Integer::intValue).toArray();
}

Execution Trace

Hash-map count

Step 1 / 3Initialize scan.

Complexity — Time O((n+m) log(n+m)); Space O(1) extra.

---

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Hash count	O(n+m)	O(min)	best if small side fits
Sort + 2p	O((n+m) log)	O(1)	canonical for sorted / streaming

When to use which

• Presorted input → 2p.
• One huge / one small → hash on smaller.
• Streamed → hash on materialized side.

✨AI Study CompanionBeta

Related problems

• Intersection of Two Arrays — set version
• Merge Sorted Array

Was this page helpful?