Leetcode 349 - Intersection of two arrays

Link to question

Question & Examples

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result 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]
Explanation: [4,9] is also accepted.

Implementation

function intersection(nums1, nums2) {
  let array = []
  for(let i = 0; i < nums1.length; i++) {
    for(let j = 0; j < nums2.length; j++) {
      if(nums1[i] === nums2[j] && !array.includes(nums1[i])) {
        array.push(nums1[i])
      }
    }
  }
  return array
}

Walkthrough

It's pretty traightforward.

1. Create a new array.
2. Start a for loop that loops over the first array + start another one that loops over the second array.
3. Check to see if the two values in their respective indices are the same && check to see if the value doesn't already exist in the array array.

Although this may be the most simple method, the time complexity is really bad.

Because we have a nested loop in an outer loop, the time complexity is O(n * m) where n and m are both the length of the respective arrays.

However, inside the inner loop, I included the array.includes() method which has a time complexity of O(k) where the k is the length of the array.

As the array grows, the includes() method takes more time --> O(min(n, m))

This means that the overall time complexity could be explained like this:

O(n * m * min(n, m))

However, there's obviously a better solution to this. We can use the hashing method.

function intersection(nums1, nums2) {
  const map = {}
  for (const num of nums1) {
    map[num] = (map[num] || 0) + 1
  }
 
  const result = []
  for (const num of nums2) {
    if (map[num]) {
      result.push(num)
      delete map[num]
    }
  }
 
  return result
}

This method (unlike the previous method), uses hashing which improves the performance.

• Building the hash map from nums1 takes O(n).
• Checking the intersection with nums2 takes O(m).

So the time complexity would be O(n + m).

Space complexity would be O(n) where n would be the number of the unique elements.

Time and Space Complexities

Time Complexity: O(n + m) | Space: O(n)