Intersection of Two Arrays II
Here again with another coding challenge from LeetCode, this one is called Intersection of Two Arrays II. I never did the first version of this problem, so hopefully I'm not missing anything.
Prompt: Intersection of Two Arrays II
Given two integer arrays
nums1andnums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
Example 1:
Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2, 2]
Example 2:
Input: nums1 = [4, 9, 5, 7, 4], nums2 = [5, 4, 9, 4, 9, 8, 4]
Output: [4, 9, 5, 4]
Explanation: [4, 5, 9, 4] is also accepted.
Stating the Problem in My Own Words
I'll be given two arrays, nums1 and nums2, which will each contain a set of numbers. My task is to return the intersection of these two arrays. This intersection is an array that contains all numbers that appear in both nums1 and nums2, in the quantity in which they appear in both arrays. The order isn't important.
So, if I'm given nums1 = [1, 2, 3, 4, 5], nums2 = [5, 3, 1], then the intersection could be [1, 3, 5] or [3, 5, 1] or [5, 3, 1].
Likewise if I'm given nums1 = [1, 1, 3, 5, 5], nums2 = [1, 3, 5, 1] then the intersection could be [1, 1, 3, 5]. Again the numbers in the intersection can be in any order, they just need to adhere to the frequency in which the numbers appear in nums1 and nums2.
Approach: Sort and Loop
The easiest way to solve this is to first sort each array (we'll go in ascending order) and then loop through both arrays, looking for matches.
First, let's sort both arrays:
function intersect(nums1, nums2) {
nums1 = nums1.sort((a, b) => a - b);
nums2 = nums2.sort((a, b) => a - b);
console.log(nums1);
// result: [4, 4, 5, 7, 9]
console.log(nums2);
// result: [4, 4, 4, 5, 8, 9, 9]
}
intersect([4, 9, 5, 7, 4], [5, 4, 9, 4, 9, 8, 4]);The next step is to initialize our intersection variable. This will start out as an empty array, and as we find numbers that occur in both sorted arrays, those numbers will be pushed into intersection. We'll be returning intersection at the very end of this function.
We'll also need to loop through nums1 and nums2. We'll do this using two counters (counter1 and counter2), one for each array, that will each count up through their respective arrays. Let's write this out — first the variable initialization and then a while loop using the two counters:
function intersect(nums1, nums2) {
nums1 = nums1.sort((a, b) => a - b);
nums2 = nums2.sort((a, b) => a - b);
let intersection = [];
let counter1 = 0;
let counter2 = 0;
while (counter1 < nums1.length && counter2 < nums2.length) {
counter1 += 1;
counter2 += 1;
}
return intersection;
}
intersect([4, 9, 5, 7, 4], [5, 4, 9, 4, 9, 8, 4]);Now that we are looping through the sorted nums1 and nums2 arrays, we need to start comparing values. We have three conditions we're looking for:
- If the two numbers are the same, then a match has been found. We can push that number into
intersectionand increment both counters to look at the next numbers in both arrays. - If the number in
nums1is less than the number innums2, then a match hasn't been found. We can incrementcounter1to look at the next value innums1. - Otherwise, the number in
nums2is less than the number innums1. A match hasn't been found, so we can incrementcounter2to look at the next value innums2.
Let's break it down with our sorted arrays:
counter1: 0
nums1:
[4, 4, 5, 7, 9]
^
counter2: 0
nums2:
[4, 4, 4, 5, 8, 9, 9]
^
intersection:
[]First iteration: 4 and 4 are the same, so we've found one match. We can add 4 to intersection and increment counter1 and counter2 (i.e., look at the next number in both arrays).
counter1: 1
nums1:
[4, 4, 5, 7, 9]
^
counter2: 1
nums2:
[4, 4, 4, 5, 8, 9, 9]
^
intersection:
[4]Second iteration: 4 and 4 are once again the same, so we have another match. We'll push 4 into intersection again and increment both counters.
counter1: 2
nums1:
[4, 4, 5, 7, 9]
^
counter2: 2
nums2:
[4, 4, 4, 5, 8, 9, 9]
^
intersection:
[4, 4]Third iteration: Okay so there's no match here, and since 5 is greater than 4, we'll leave counter1 where it is and increment counter2. Nothing gets pushed into intersection.
counter1: 2
nums1:
[4, 4, 5, 7, 9]
^
counter2: 3
nums2:
[4, 4, 4, 5, 8, 9, 9]
^
intersection:
[4, 4]Fourth iteration: We found another match! 5 will get pushed into intersection and we'll look at the next number in both arrays.
counter1: 3
nums1:
[4, 4, 5, 7, 9]
^
counter2: 4
nums2:
[4, 4, 4, 5, 8, 9, 9]
^
intersection:
[4, 4, 5]Fifth iteration: No match here, and this time 7 (counter1) is less than 8 (counter2), so we'll increment counter1 for the next comparison. Nothing gets pushed into intersection.
counter1: 4
nums1:
[4, 4, 5, 7, 9]
^
counter2: 4
nums2:
[4, 4, 4, 5, 8, 9, 9]
^
intersection:
[4, 4, 5]Sixth iteration: No match here again, but counter2 has the smaller value, so we'll increment that. Nothing gets pushed into intersection.
counter1: 4
nums1:
[4, 4, 5, 7, 9]
^
counter2: 5
nums2:
[4, 4, 4, 5, 8, 9, 9]
^
intersection:
[4, 4, 5]Seventh iteration: We found another match! 9 gets pushed into intersection, and we increment both counters.
counter1: 5
nums1:
[4, 4, 5, 7, 9]
^ // end of array!
counter2: 6
nums2:
[4, 4, 4, 5, 8, 9, 9]
^
intersection:
[4, 4, 5, 9] // return this!End of function: At this point we've reached the end of nums1, meaning there's no way we can have any more matching elements. All we need to do now is return intersection.
Solution: Intersection of Two Arrays II
So here is what the function looks like with the above logic written out:
function intersect(nums1, nums2) {
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
let intersection = [];
let counter1 = 0;
let counter2 = 0;
while (counter1 < nums1.length && counter2 < nums2.length) {
if (nums1[counter1] === nums2[counter2]) {
intersection.push(nums1[counter1]);
counter1 += 1;
counter2 += 1;
} else if (nums1[counter1] < nums2[counter2]) {
counter1 += 1;
} else {
counter2 += 1;
}
}
return intersection;
}Big O of this Solution
I believe that the comparison logic in the above solution runs at O(n + m) time in the worst-case scenario, where n is the length of nums1 and m is the length of nums2. I say the "worst-case scenario" because realistically it mostly depends on how long the shortest array is. If n is a million items long but m only contains 1 item, then the iteration will only run once. However, if nums1 and nums2 are each 10 items long, then we would need to make 10 comparisions for each array, totalling up 20 comparions, hence n + m. You can try this yourself by passing nums1 and nums2 as completely different arrays. Try all odd numbers for nums1 and all even numbers for nums2.
However, that's not even the entire picture. We also need to take into account the .sort() operations that kick the whole thing off. This sorting is crucial for our multiple pointer solution to work. Determining the Big O of JavaScript's .sort() method is difficult. Different engines do different things, and even the V8 engine seems to take a different approach for longer arrays than it does for short arrays. Here's a blog post about the complexity of Array.sort().
I'm terrible at compounding the complexity of multiple operations, but if the sorting algorithm is O(n²) for an array that's less than 10 items long (like all of the examples above), then all together I think we are looking at a worst case of O(2(n² + m²)). 2 because we have to go through each array twice (once for sorting, which gives us the ²s, and once for comparison).
Again, I might be wrong about how all of these operations come together for Time Complexity. Feel free to email me at joey@joeyreyes.dev if you're more knowledgeable about the Big O of the above solution and I'll be happy to issue a correction. Also, if you have a different solution I'd love to hear from you and write about it here on my blog. Otherwise, thank you for reading!