A simple algorithm to find duplicates in two arrays

findDuplicates.js

/*

time: O(m + n)
space: O(n) // whichever is smaller

arr1 = [ 1, 2, 3, 5, 6, 7 ]
                        ^ 
arr2 = [ 3, 6, 7, 8, 20 ]
               ^
arr3 = [ 3, 6, 7 ]

no match
- increment the index of whichever is smaller

match
- increment both
- add to results

*/


function findDuplicates(arr1, arr2) {
  let results = []
  let indexA = 0
  let indexB = 0
  let length = arr1.length + arr2.length
  
  for (let i = 0; i < length; i++) {
    if (indexA >= arr1.length || indexB >= arr2.length) {
      break
    }
    
    if (arr1[indexA] === arr2[indexB]) {
      results.push(arr1[indexA])
      indexA++
      indexB++
    } else if (arr1[indexA] < arr2[indexB]) {
      indexA++
    } else {
      indexB++
    }
  }
  
  return results
}

findDuplicatesWithLargerArray.js

/*
case when m is significantly larger than n

m = 10 
n = 100 = 10 * 10 = m^2

time: O(m + n) = O(m^2)
space: O(m)

time: O(m log n)
space: O(m)

O(n log n) < O(n^2)

- loop over smaller
- if value is contained in larger
  - add to results

- use array.includes(value) or
- use binary search to find if value is in larger

*/

function findDuplicatesWithLargerArray(arr1, arr2) {
  let smaller 
  let larger
  let results = []
  
  if (arr1.length < arr2.length) {
    smaller = arr1
    larger = arr2
  } else if ((arr1.length > arr2.length)) {
    smaller = arr2
    larger = arr1
  } else {
    smaller = arr1
    larger = arr2
  }
  
  for (value of smaller) {
    console.log(value)
    if (isValueInArray(value, larger)) {
      results.push(value)
    }
  }
  
  return results
}

const isValueInArray = (value, array) => {
  let start = 0
  let end = array.length
  
  while (end >= start) {
    let mid = Math.floor((end - start) / 2) + start
    
    if (array[mid] === value) {
      return true
    } else if (array[mid] > value) {
      end = mid - 1
    } else {
      start = mid + 1
    }
  }
  
  return false
}