Coding Challenge Practice - Question 71

Source: Dev.to

Problem Statement

Find the elements that exist in both arrays, given two sorted arrays.

Approach

Because the arrays are sorted, we can walk through them simultaneously using two pointers:

1. Start both pointers at the beginning of their respective arrays (i = 0, j = 0).
2. Compare the current elements:
   • If they are equal, the element is present in both arrays – add it to the result and advance both pointers.
   • If the element in the first array is smaller, advance the first pointer (i++).
   • If the element in the second array is smaller, advance the second pointer (j++).
3. Continue until one of the pointers reaches the end of its array.

Implementation

function intersect(arr1, arr2) {
  let i = 0;
  let j = 0;
  const result = [];

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] === arr2[j]) {
      result.push(arr1[i]);
      i++;
      j++;
    } else if (arr1[i] < arr2[j]) {
      i++;
    } else {
      j++;
    }
  }

  return result;
}