loading...

Finding the Intersection of Two Arrays

alisabaj profile image Alisa Bajramovic Updated on ・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 of the day is a pretty straightforward one: given two arrays, return their intersection. For example, if you were given nums1 = [3, 4, 5, 1, 3] and nums2 = [1, 2, 3, 5], you'd want to write a function that returns [1, 3, 5].

I like this problem because there's lots of variations on it--What if the arrays were already sorted? What if you want to optimize memory, but not space? What if one array were significantly longer than another?

My approach

For this version of the algorithm, I'll use a hash. I find myself often using hashes in my daily algorithms because they don't take up much space or time, and you can be really creative in how you use them.

In this problem, I'll start by taking each number of the first array and putting it into a hash as the key values. If a number is a repeat and has already been seen, and therefore its key already exists in the hash, I'll increment its value by 1.

Then, I'll initialize an empty array, which I'll want to return at the end of the function. I'll go through the second given array, checking each number in it. If that number is a key in the hash, and it has a value greater than 0, I'll put it in the result array, which shows that that number was found in both inputted arrays. I'll also decrement the value in the hash. Finally, I'll return the result.

The code

The first thing I'll do is initialize a hash that the numbers from num1 will go into. Then, I'll use a for-of loop to walk through the elements of nums1.

function intersect(nums1, nums2) {
  let num1Hash = {};
  for (let num of nums1) {
    //...
  }
  //...
}

If the hash already has the number, then we can just increment its value. If it doesn't, then we can create a new key in the hash as that number, and set its value equal to 1.

function intersect(nums1, nums2) {
  let num1Hash = {};
  for (let num of nums1) {
    if (num1Hash[num]) {
      num1Hash[num]++;
    } else {
      num1Hash[num] = 1;
    }
  }

  //...
}

At this point, if the input array were [3, 4, 5, 1, 3], then num1Hash would equal {'1': 1, '3': 2, '4': 1, '5': 1}.

Now, we'll want to initialize an array, which is what we'll be returning at the end. We can call this array 'result', and can write the return line at the bottom of the function.

function intersect(nums1, nums2) {
  let num1Hash = {};
  for (let num of nums1) {
    if (num1Hash[num]) {
      num1Hash[num]++;
    } else {
      num1Hash[num] = 1;
    }
  }

  let result = [];

  //...
  return result;
}

Now, we'll want to go through each element in nums2. We want to check if the hash array has that element, and if its value is greater than 0. The reason that a key could have a value equal to 0 is that, inside the if statement, we will be decrementing values if the key has been found.

function intersect(nums1, nums2) {
  let num1Hash = {};
  for (let num of nums1) {
    if (num1Hash[num]) {
      num1Hash[num]++;
    } else {
      num1Hash[num] = 1;
    }
  }

  let result = [];

  for (let num of nums2) {
    if (num1Hash[num] && num1Hash[num] > 0) {
      //...
    }
  }
  return result;
}

As I mentioned above, if the num is in the hash, and the value is greater than 0, then the num should be pushed to the result array, and the value in the hash should be decremented.

function intersect(nums1, nums2) {
  let num1Hash = {};
  for (let num of nums1) {
    if (num1Hash[num]) {
      num1Hash[num]++;
    } else {
      num1Hash[num] = 1;
    }
  }

  let result = [];

  for (let num of nums2) {
    if (num1Hash[num] && num1Hash[num] > 0) {
      result.push(num);
      num1Hash[num]--;
    }
  }
  return result;
}

--

Please let me know in the comments if you have any questions, or alternate solutions to this problem!

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