Intersection of Two Arrays I and II

by linkjobai

HTML

<!DOCTYPE html>
<html lang="en"><head><meta charset="utf-8"><title>Intersection of Two Arrays I and II: Hash Set, Counter, or Two Pointers</title>
<style>body{font-family:Georgia,serif;max-width:760px;margin:40px auto;padding:0 16px;line-height:1.6;color:#222}pre{background:#f4f4f4;padding:12px;overflow:auto}code{font-family:Menlo,monospace}</style></head>
<body>
<h1>Intersection of Two Arrays I and II: Hash Set, Counter, or Two Pointers</h1>
<p>LeetCode 349 and 350 look like warm-ups, but interviewers use them to see whether you pick a data structure on purpose and whether you can handle the follow-up questions about sorted input and data that does not fit in memory.</p>
<h2>349: unique values only</h2>
<p>Put the smaller array into a set, then walk the other array and collect values found in the set, removing each one after the first hit so it is reported once.</p>
<pre><code>def intersection(a, b):
    if len(a) &gt; len(b):
        a, b = b, a
    seen = set(a)
    out = []
    for x in b:
        if x in seen:
            out.append(x)
            seen.remove(x)
    return out</code></pre>
<p>Time is O(n + m) and extra space is O(min(n, m)).</p>
<h2>350: keep duplicates</h2>
<p>Now each value appears as many times as it shows up in both arrays, so a set is not enough. Count the smaller array, then decrement as you match.</p>
<pre><code>from collections import Counter

def intersect(a, b):
    if len(a) &gt; len(b):
        a, b = b, a
    count = Counter(a)
    out = []
    for x in b:
        if count[x] &gt; 0:
            out.append(x)
            count[x] -= 1
    return out</code></pre>
<h2>Follow-up 1: both arrays are already sorted</h2>
<p>Drop the hash map and use two pointers. Advance the pointer at the smaller value; on equal values record the match and advance both. This is O(n + m) time with O(1) extra space.</p>
<pre><code>def intersect_sorted(a, b):
    i = j = 0
    out = []
    while i &lt; len(a) and j...