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) > 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) > len(b):
a, b = b, a
count = Counter(a)
out = []
for x in b:
if count[x] > 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 < len(a) and j...