Skip to content

Instantly share code, notes, and snippets.

@lumie31
Created July 28, 2022 11:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lumie31/1698f5d90ec77633453e115672177a36 to your computer and use it in GitHub Desktop.
Save lumie31/1698f5d90ec77633453e115672177a36 to your computer and use it in GitHub Desktop.
Given two arrays A and B, return the indices at which the two arrays intersect. If the two arrays have no intersection at all, return null.
// Brute force - O(n^2)
const findIntersection = (arr1, arr2) => {
for (let i = 0; i < arr1.length; i++) {
for (let j = 0; j < arr2.length; j++) {
if (arr1[i] === arr2[j]) {
return [i, j]
}
}
}
return null
}
// Optimized solution - O(n)
const findIntersection = (arr1, arr2) => {
let store = {}
for (let i = 0; i < arr1.length; i++) {
store[arr1[i]] = i
}
for (let j = 0; j < arr2.length; j++) {
if (arr2[j] in store) {
return [store[arr2[j]], j]
}
}
return null
}
// Provided the arrays are sorted - O(n)
const findIntersection = (arr1, arr2) => {
let i = 0, j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] === arr2[j]) {
return [i, j]
} else if (arr1[i] < arr2[j]) {
i++
} else {
j++
}
}
return null
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment