Day 12 of 250: LeetCode 349 Intersection of Two Arrays | Hashing for Fast Lookup Explained

Coming Off Yesterday: From Streak Tracking to Membership Testing

On Day 11, we tracked the longest consecutive run of ones in a binary array using two variables and a single pass. The state we maintained was linear: a counter that grew and reset as we moved through the array.

Today the problem is different in character. We are not scanning a single array; we are comparing two arrays and asking which values appear in both. The core operation is membership testing: "Is this element from nums2 somewhere in nums1?" If we do that test naively by scanning nums1 for every element of nums2, we get O(n × m) time. If we preprocess nums1 into a hash map, each lookup drops to O(1), and the whole algorithm becomes O(n + m).

There is also a second requirement: the result must contain only unique values. Even if a number appears multiple times in both arrays, it should appear exactly once in the output. The elegant part of the hash approach is that we can enforce uniqueness without a separate deduplication step. We delete each matched entry from the hash the moment we add it to the result, so the same value can never be matched again.

Day 12 is LeetCode 349: Intersection of Two Arrays. It is tagged Easy, and it is a clean demonstration of two ideas working together: hash maps for O(1) lookup, and deletion as a mechanism for enforcing uniqueness.

Problem Statement

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

Example 1:

Input:  nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2]

Example 2:

Input:  nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
Output: [9, 4]

Constraints:

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

The Core Insight: Use a Hash Map for O(1) Lookup and Deletion for Uniqueness

Here are the two observations that unlock the optimal solution together.

The first is about speed. Checking whether a number from nums2 exists in nums1 by scanning nums1 linearly is O(n) per check. If nums2 has m elements, the total cost is O(n × m). But if we load nums1 into a hash map first, each membership check becomes an O(1) key lookup. The total cost drops to O(n) to build the map plus O(m) to check all of nums2, giving us O(n + m).

The second is about uniqueness. The result cannot contain duplicate values even if an element appears multiple times in both input arrays. We could collect all matching elements and then deduplicate using a Set. But there is a cleaner way: every time we find a match, we delete that key from the hash map immediately. The next time we encounter the same value in nums2, the key no longer exists, so no match is found and the value is not added again. Deletion serves as the deduplication mechanism, requiring no separate pass.

The brute force approach that most people reach for first uses a nested loop:

// Brute force: O(n × m) time
const result = [];
for (let x of nums2) {
    if (nums1.includes(x) && !result.includes(x)) {
        result.push(x);
    }
}

This has two problems: nums1.includes(x) is O(n) and result.includes(x) is O(output size). Both can be eliminated with the hash approach.

First Instincts vs. Correct Thinking

The most common first instinct is to sort both arrays and use two pointers to find common elements. That works and gives O(n log n + m log m) time with O(1) extra space (excluding the output). It is a legitimate approach worth knowing.

But the hash map approach is better when the arrays are not sorted and when average-case O(n + m) is acceptable. More importantly, the hash approach has a natural deduplication mechanism built in through deletion, while the two-pointer approach requires careful handling of duplicates during the pointer advancement phase.

The mental model shift from brute force to hash is the same one we made on Day 1 with Two Sum: stop re-scanning the input for every query. Store what you have seen in a structure that answers membership questions in O(1). Then iterate once over the second input, querying against that structure.

The uniqueness requirement is the new wrinkle here compared to Day 1. Deletion is the implementation of the rule "each value can only be added to the result once." Once a value is matched and added, its key in the hash is gone, and any future encounter of that same value finds no entry and is skipped.

Understanding the Approach

We split the algorithm into two phases.

In the first phase, we build a hash map from nums1. For every element in nums1, we store its frequency. The exact frequency does not matter for correctness here since we only need to know whether a key exists, but tracking it costs nothing extra and opens the door to solving the related problem (LeetCode 350: Intersection of Two Arrays II) with minimal changes.

In the second phase, we iterate through nums2. For each element, we check whether its key exists in the hash map. If it does, we push the element into our result array and immediately delete the key from the hash map. The deletion is what prevents duplicates: if the same value appears later in nums2, the key will be gone and the lookup will fail.

We return the result array after processing all of nums2.

Deep Dry Run: Every Step Explained

We will trace through nums1 = [1, 2, 2, 1] and nums2 = [2, 2] completely.

Initial state:

nums1 = [1, 2, 2, 1]
nums2 = [2, 2]

hs     = {}
result = []

Phase 1: Build Hash Map from nums1

num = 1 → 1 not in hs → hs[1] = 1
num = 2 → 2 not in hs → hs[2] = 1
num = 2 → 2 in hs     → hs[2] = 2
num = 1 → 1 in hs     → hs[1] = 2

Final hs = { 1: 2, 2: 2 }

Every element of nums1 is now stored in the hash map with its frequency. The map tells us which values exist in nums1.

Phase 2: Iterate Through nums2

Iteration 1 (num = 2):

nums2 = [2,  2]
         ^
         current

hs = { 1: 2, 2: 2 }

Lookup: hs[2] = 2 → exists (truthy).
Action: push 2 to result, delete hs[2].

result = [2]
hs     = { 1: 2 }

The value 2 is found in the hash map. It is added to the result and immediately deleted. The map no longer contains 2.

Iteration 2 (num = 2):

nums2 = [2,  2]
             ^
             current

hs = { 1: 2 }

Lookup: hs[2] = undefined → does not exist (falsy).
Action: skip.

result = [2]
hs     = { 1: 2 }

The same value 2 is encountered again. But the key was deleted in the previous iteration, so the lookup fails. This element is silently skipped. No duplicate is added.

Loop ends. All of nums2 has been processed.

return result = [2]

Final output: [2]. Correct. The value 2 appears in both arrays and appears exactly once in the result.

Bonus trace for Example 2: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]

Phase 1 builds hs = { 4: 1, 9: 1, 5: 1 }.

Phase 2 iteration by iteration:

num = 9 → hs[9] exists → result = [9], delete hs[9] → hs = { 4:1, 5:1 }
num = 4 → hs[4] exists → result = [9, 4], delete hs[4] → hs = { 5:1 }
num = 9 → hs[9] missing → skip
num = 8 → hs[8] missing → skip
num = 4 → hs[4] missing → skip

Output: [9, 4]. Correct. Both 9 and 4 appear once each despite appearing multiple times in nums2.

What Made It Work: The Deeper Why

1. Hash map lookup is O(1) on average. Checking whether a key exists in a JavaScript object or hash map is constant time on average, not linear. This is the entire reason for the speedup over the brute force scan. The O(n) preprocessing cost to build the map is paid once and amortizes across all m lookups.

2. Deletion is a zero-cost deduplication mechanism. Adding a step after the result is complete to remove duplicates, such as spreading into a Set, is O(output size). Deleting from the hash at match time instead costs O(1) per deletion and requires no additional pass. The deduplication happens naturally as part of the same iteration.

3. Only nums1 needs to be in the hash map; nums2 is iterated directly. The intersection operation is symmetric in terms of its result, but the implementation is not symmetric. We load the smaller or more convenient array into the hash and iterate through the other. Here, any order works, but in practice, loading the smaller array saves space.

4. Frequency tracking is not required for correctness here, but it is a useful extension. The intersection result only requires presence, not frequency. So hs[num] = 1 for every element in nums1 would be sufficient. Tracking frequency as shown in the code opens the door directly to LeetCode 350, where the intersection counts duplicates. The cost of tracking frequency is zero additional complexity.

The Code

var intersection = function(nums1, nums2) {
    let hs = {};

    for (const num of nums1) {
        if (hs[num]) {
            hs[num] += 1;
        } else {
            hs[num] = 1;
        }
    }

    let result = [];
    for (const num of nums2) {
        if (hs[num]) {
            result.push(num);
            delete hs[num];
        }
    }

    return result;
};

The first for...of loop builds the hash map hs from nums1. For each element, if the key already exists we increment its count; otherwise we initialize it to 1. This produces a frequency map of every value in nums1.

The second for...of loop iterates through nums2. The condition if (hs[num]) is truthy when the key exists in the map with a non-zero value. When matched, we push the number to result and call delete hs[num] to remove the key entirely. This means future encounters of the same number in nums2 will find hs[num] undefined, which is falsy, and they will be skipped.

We return result after the second loop completes. The result contains each common value exactly once, in the order they were first encountered in nums2.

One important note: if (hs[num]) is falsy not only when the key does not exist, but also when hs[num] === 0. In this problem that cannot happen because we only store positive counts and delete rather than decrement. But in LeetCode 350, where you decrement rather than delete, you would need if (hs[num] > 0) instead to avoid treating a zeroed-out key as a missing key.

Complexity Analysis

Common Mistakes

Mistake 1: Using if (hs[num]) when values could be 0.

In this specific problem, all values are between 0 and 1000, and nums[i] could be 0. If an element with value 0 exists in nums1, then hs[0] = 1 after the first phase. But in the second phase, if (hs[0]) evaluates hs[0] as a number... the frequency 1, which is truthy. So it works correctly here.

However, if the problem stored a boolean presence flag like hs[num] = true, and you later decremented to hs[num] = 0 instead of deleting, if (hs[num]) would be falsy for 0 even though the key exists. Always use if (hs[num] > 0) or explicit if (num in hs) when the stored values could be zero or falsy.

Mistake 2: Checking result.includes(x) instead of using hash deletion for deduplication.

// Slow: O(output size) per check
if (nums1.includes(x) && !result.includes(x)) {
    result.push(x);
}

result.includes(x) scans the entire result array on every iteration. For large outputs this becomes O(n × m). Hash deletion achieves the same deduplication at O(1) per element.

Mistake 3: Decrementing instead of deleting to handle duplicates.

// Wrong for LeetCode 349: leads to double-counting if count stays positive
if (hs[num] > 0) {
    result.push(num);
    hs[num]--;  // count drops to 1, still truthy, still matchable
}

For this problem, where each output element must be unique, decrementing is wrong. If hs[num] was 2 and nums2 contains the same value twice, the first match decrements to 1 (still truthy) and the second match decrements to 0 (falsy), but the element would have already been added twice. For LeetCode 349, always delete. For LeetCode 350 (which counts duplicates), decrement.

Mistake 4: Building the hash from the wrong array and iterating through the wrong one.

If you build the hash from nums2 and iterate through nums1, the result is still correct since intersection is symmetric. But the order of elements in the result will differ. Some candidates flip the arrays accidentally and are confused when their output order does not match the expected output. Both orderings are valid since the problem allows any order.

Mistake 5: Forgetting that delete removes the key entirely, not just zeroing the value.

After delete hs[num], hs[num] is undefined, not 0. undefined is falsy, so subsequent if (hs[num]) checks fail correctly. This is the desired behavior. Candidates who are not familiar with JavaScript's delete operator sometimes assume it sets the value to null or 0, which would behave differently under if (hs[num]).

Interview Tips

Step 1: State the two requirements before touching the approach. Say: "The problem has two constraints I need to satisfy: the lookup needs to be fast, and the result must have unique values. A hash map handles both. O(1) lookup replaces linear scanning, and deleting matched keys prevents duplicates without a separate deduplication pass."

Step 2: Explain why you build the hash from nums1 and iterate nums2. Say: "Either direction works for correctness since intersection is symmetric. I load nums1 into the hash and scan nums2 because that separates the setup phase from the query phase clearly."

Step 3: Make the deletion mechanism explicit before writing code. Say: "When I find a match, I delete the key from the hash immediately. So if the same value appears again in nums2, the lookup fails and I do not add it twice. The deletion is the deduplication."

Step 4: Trace through one example where a value appears multiple times. Use nums2 = [2, 2] and show that the first 2 is matched and deleted, and the second 2 finds nothing. This demonstrates that you understand the mechanism, not just the code.

Step 5: Mention the related problem as a follow-up. Say: "If the interviewer asks for LeetCode 350, where duplicates in the result are allowed up to the count in both arrays, I would change delete hs[num] to hs[num]-- and use if (hs[num] > 0) to avoid falsy zero values."

Where This Pattern Appears Next

LeetCode 350: Intersection of Two Arrays II is the direct follow-up. The output can include duplicates up to the minimum count in both arrays. The code changes from delete hs[num] to hs[num]--, and the condition changes from if (hs[num]) to if (hs[num] > 0). Understanding today's deletion mechanism makes that change feel obvious.

LeetCode 1: Two Sum uses the same hash map pattern in reverse: instead of checking membership for a second array, it checks whether the complement of the current element has been seen earlier in the same array. The lookup structure and the reasoning are identical.

LeetCode 217: Contains Duplicate asks whether any value appears more than once in a single array. Loading elements into a hash or Set and checking for pre-existing keys is the direct application of today's membership-testing instinct.

LeetCode 202: Happy Number uses a Set to detect whether a value has been seen before in a sequence. The membership-testing pattern from today generalizes naturally to cycle detection problems where you need to know whether a computed value has been encountered previously.

Key Takeaways

Hashing simplifies intersection problems by replacing linear scans with constant-time lookups. The brute force approach scans nums1 for every element in nums2. Loading nums1 into a hash map converts every one of those O(n) scans into an O(1) key lookup. The preprocessing cost is paid once, not per query.

Deletion is a first-class deduplication mechanism. Rather than collecting all matches and then deduplicating, we delete matched keys at the moment of matching. This enforces the uniqueness constraint inline, with no extra pass and no extra data structure.

Frequency tracking is optional here but costs nothing extra. Storing frequencies instead of just boolean presence makes the hash map immediately reusable for LeetCode 350 with a one-line change. Thinking about adjacent problems while solving the current one is a habit that impresses interviewers.

Clean logic beats clever tricks. Two loops, one hash map, one result array. No sorting, no nested loops, no Set operations, no spread operators. The solution is readable, correct, and efficient. Elegance here comes from choosing the right data structure, not from compressing the code.

Closing

Day 12 is done. A problem that requires two things simultaneously, fast lookup and unique results, turns out to need one data structure and one line of cleanup code. The hash map gives us the lookup, and the delete gives us the uniqueness, without requiring any separate phase for either.

On Day 13, we continue growing the toolkit. The hash map instinct we have now seen on multiple problems, from Two Sum to Majority Element to today's intersection, will keep showing up as one of the most fundamental building blocks in array and string problems.

If the "delete as deduplication" framing clicked for you, or if you want to see how today's code changes for LeetCode 350, drop a comment below.

See you on Day 13. 🚀

This post is part of my 250 Days DSA Challenge, solving one problem every day with a focus on intuition, patterns, and interview ready thinking.