LESSON 273 OF 438 · HASH TABLE

Intersection of Two Arrays in JavaScript: Hash Table in O(n + m)

Practice O(n + m) Read the full explanation

Given two integer arrays first and second, return an array of their intersection. Each element in the result must be unique, and the result must be sorted in ascending order.

Example 1:

Input: first = [1,2,2,1], second = [2,2]
Output: [2]

Example 2:

Input: first = [4,9,5], second = [9,4,9,8,4]
Output: [4,9]
Explanation: 4 and 9 are in both arrays. Each appears twice in second, but only once in the result.

Constraints:

1 <= first.length, second.length <= 1000
-1000 <= first[i], second[i] <= 1000

Note:

Your algorithm should run in O(n + m) time, plus the time to sort the shared numbers, where n and m are the lengths of first and second.

STEP 1 OF 12

Guided

Ctrl + Enter to check

JAVASCRIPT · HASH TABLE

Intersection Of Two Arrays in JavaScript, explained

Problem overview

The method intersection(first, second) receives two arrays of integers and returns the numbers that appear in both. Each shared number appears once in the result, however many times it occurs in the inputs, and the result is listed from the smallest number to the largest.

With first = [1, 2, 2, 1] and second = [2, 2], only 2 is in both arrays, so the answer is [2]. With first = [4, 9, 5] and second = [9, 4, 9, 8, 4], both 4 and 9 are shared. Each appears twice in second but only once in the result, so the answer is [4, 9]. Each array has between 1 and 1,000 numbers, and every number is between -1000 and 1000.

The lesson asks for O(n + m) time, plus the time to sort the shared numbers, where n and m are the lengths of the two arrays.

Approach: remember one array, scan the other

The direct method checks every number of first against every number of second, which takes O(n × m) time. A hash table removes the inner scan. An object answers "is this number in the set?" in constant time on average, so one pass over each array is enough.

The plan has three parts:

Put every number of the shorter array into an object as a key, each with the value 0.
Walk through the longer array. For each number that is a key of the object, add 1 to its value. Numbers that are not keys are ignored.
Collect the keys whose value is above 0. Those are exactly the numbers that occur in both arrays. Sort them, and that is the answer.

Using the shorter array for the keys keeps the object as small as possible. The result is the same in either direction, because "appears in both" is symmetric.

Take first = [4, 9, 5] and second = [9, 4, 9, 8, 4]. The first array is shorter, so the object starts as { 4: 0, 9: 0, 5: 0 }. Scanning second: 9 raises its value to 1, 4 raises its value to 1, 9 to 2, 8 is not a key and is skipped, and 4 goes to 2. The object ends as { 4: 2, 9: 2, 5: 0 }. The value of 5 is still 0, so it is not shared. The shared numbers are 4 and 9.

Step by step

Alias the two inputs as nums1 and nums2, declared with let. The next step may swap them, and swapping these two variables leaves the caller's arrays alone.
Create an empty object d with const. It will map numbers to counts.
Make nums1 the shorter array. If nums1.length > nums2.length, swap the two with destructuring. The object then has as few keys as possible.
Loop over nums1 with for...of.
Set d[i] = 0 for each number. A key that is already there is simply set to 0 again, so duplicates in nums1 do no harm.
Loop over nums2 with a second for...of.
Skip numbers that aren't keys. The test !(i in d) is true for a number that nums1 doesn't contain, and continue moves on to the next number.
Count the hits. In the else branch, d[i] becomes d[i] + 1. The count itself doesn't matter, only whether it rose above 0.
Prepare the result as an empty array named result.
Loop over Object.entries(d) and destructure each entry into k, the key, and val, the count.
Keep the shared numbers. When val > 0, push Number(k). The conversion is needed because object keys are always strings, so k is "4" and not 4.
Sort and return. result.sort((a, b) => a - b) orders the numbers from smallest to largest, and the method returns result.

The solution in JavaScript

class Solution {
    /**
    * @param {number[]} first
    * @param {number[]} second
    * @return {number[]}
    */
    intersection(first, second) {
        let nums1 = first, nums2 = second;
        const d = {};
        if (nums1.length > nums2.length) {
            [nums1, nums2] = [nums2, nums1];
        }
        for (const i of nums1) {
            d[i] = 0;
        }
        for (const i of nums2) {
            if (!(i in d)) continue;
            else d[i] = d[i] + 1;
        }
        const result = [];
        for (const [k, val] of Object.entries(d)) {
            if (val > 0) result.push(Number(k));
        }
        result.sort((a, b) => a - b);
        return result;
    }
}

Some JavaScript details worth a closer look:

Object keys are strings. d[4] and d["4"] are the same property, and Object.keys returns "4", a string. That is why the code converts with Number(k) before pushing.
The in operator. 4 in d checks whether d has a property named "4". The number is converted to a string for the check, so it works with numeric keys. A plain truthiness test such as if (d[i]) would be wrong: a number whose count is 0 is falsy, and so is every key of the first pass.
Why the sort is needed. Looping over an object's keys does not give numeric order. Keys that look like non-negative integers come first in ascending order, but negative numbers, such as "-1", are ordinary string keys and follow in the order they were added. For the keys 10, 9, -1 and -5 added in that order, Object.keys gives ["9", "10", "-1", "-5"]. The sort fixes the order.
The comparator is required. sort() with no argument compares the numbers as text, so 10 would come before 9: [10, 9, 1].sort() gives [1, 10, 9]. The comparator (a, b) => a - b compares them as numbers.
Swapping variables. [nums1, nums2] = [nums2, nums1] exchanges the two variables without a temporary one. It changes which array each name points to, not the arrays themselves.
Destructuring in for...of. Object.entries(d) returns an array of [key, value] pairs, and const [k, val] unpacks each pair.

Complexity

Time: O(n + m) plus the sort. Filling the object takes one pass over the shorter array, and counting takes one pass over the longer one. Each lookup and update on the object takes constant time on average. Reading the entries visits at most as many keys as the shorter array has numbers. The final sort works on the shared numbers only, which is at most min(n, m) of them, so it costs O(r log r) where r is the size of the result.

Space: O(min(n, m)). The object holds one key per distinct number of the shorter array, and the result is no bigger. With values between -1000 and 1000, there are never more than 2001 keys.

Edge cases and common mistakes

No shared numbers. For [1] and [2], every count stays 0 and the method returns [].
Duplicates. [1, 2, 2, 1] and [2, 2] give [2], not [2, 2]. The object has one key per number, so each shared number shows up once.
Negative numbers and zero. They work as keys like any other number. For [-1, 10, 9, -5] and [9, 10, -5, 3] the answer is [-5, 9, 10]. Zero is a valid key too, and its count of 0 at the start must not be mistaken for "missing".
Returning strings. Without Number(k) the result would be ["4", "9"], which is not equal to [4, 9].
Forgetting the comparator. A result such as [10, 9] would be sorted as text. Always pass (a, b) => a - b when sorting numbers.
Asking the wrong question of the counts. A key that was added but never hit has the value 0 and must not be in the result. Checking val > 0, not just that the key exists, is what separates the two.

Testing

first = [1, 2, 2, 1], second = [2, 2] gives [2].
first = [4, 9, 5], second = [9, 4, 9, 8, 4] gives [4, 9].
first = [1], second = [2] gives [].
first = [-1, 10, 9, -5], second = [9, 10, -5, 3] gives [-5, 9, 10].

Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free