loading...

Finding the Intersection of Two Arrays

alisabaj profile image Alisa Bajramovic ・3 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Today's algorithm is the Intersection of Two Arrays problem:

Given two arrays, write a function to compute their intersection.

Each element in the result has to be unique, and the result can be in any order.

For example, if the two arrays were [3, 5, 3, 2] and [3, 5, 3], the output should be [3, 5], because those are the two unique elements found in both arrays.

This problem is a good instance to make use of sets. A set is an object of unique values, and are particularly useful in problems where you're told to return unique elements. You can learn more about sets here.

In this post, I'll be discussing how I want to approach this problem, then coding the solution in JavaScript.

Approaching the Problem

In this problem, we're given two arrays, which may both have repeating numbers in them, and we only want to return unique, shared values. One way to solve this is by turning the first array into a set, which will remove any duplicate values.

Turning an array into a set is actually a very short process. Let's say you had an array called arr1, which was equal to [2, 4, 4], and wanted to create a set based on that array:

  const set1 = new Set(arr1)

Based on the above statement, set1 will equal {2, 4}.

Once we turn the first given array into a set, we can then go through each element of the second given array, and check if it's in the set. If it is, we'll add it to a result array, which we'll return at the end. We'll also want to remove that element from the set, so that if the second array has a duplicate value, we don't add it to the result array twice.

To check if a set has an element, we can use the has() method, which returns a boolean value (true or false). For example, if we're still working with set1 from above:

  const arr1 = [2, 4, 4]
  const set1 = new Set(arr1) // {2, 4}
  set1.has(2) // will return true
  set1.has(5) // will return false

To remove an element from a set, we can use the delete() method, which removes a specific element from a set. To continue with the same example:

  const arr1 = [2, 4, 4]
  const set1 = new Set(arr1) // {2, 4}
  set1.delete(2) // set1 = {4}

Coding the Solution

With the above methods in mind, we can start out by creating a new set based on nums1, which is the first inputted array. We can do this by setting a new variable called set equal to new Set(nums1).

We also can create a new array called result, which we'll start as an empty array. This array will be returned at the end of the function, so we can include the result statement now.

function intersection2(nums1, nums2) {
  let set = new Set(nums1);
  let result = [];
  //...
  return result;
}

Now, we'll want to check each value of nums2 to see if it's in set. To do this, we can set up a for loop, which will iterate through each value of nums2, and therefore will go from 0 until the length of the nums2 array.

function intersection2(nums1, nums2) {
  let set = new Set(nums1);
  let result = [];
  for (let i = 0; i < nums2.length; i++) {
    //...
  }
  return result;
}

Inside the for loop, we'll want to check if the set has each element of nums2. Each element of nums2 is accessed with nums2[i]. We then can create a conditional statement to see if the set has that element, using set.has(nums2[i]).

If this returns true, then we'll want to do two things: first, we'll want to add the element to the result array, using .push(). We'll then want to delete that element from set, so that we don't add duplicate values to the result array.

function intersection2(nums1, nums2) {
  let set = new Set(nums1);
  let result = [];
  for (let i = 0; i < nums2.length; i++) {
    if (set.has(nums2[i])) {
      result.push(nums2[i]);
      set.delete(nums2[i]);
    }
  }
  return result;
}

This will return an array containing unique values shared by both arrays.

--

Let me know if you have any questions or alternate solutions to finding the intersection of two arrays.

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide
 

function intersection1(array1,array2){
// Use polyfill if you are concerning about IE11
//or
// go with indexOf instead of includes
return array1.filter(value => array2.includes(value));

}

intersection1([2,4,5,4] , [0,5]) // will result [5]

(: Happy coding :)