List Intersection / List Overlap Algorithm

Given two lists of elements, how do you find which items appear in both lists? The algorithm for Day 4 of 30 Days of Algorithms demonstrates how to find the overlap of two lists (list intersection).

Problem : We have a list of students and the list of classes each student is taking. How can we efficiently find classes shared by each pairing of students?

Find The List Intersection

To find the shared items between the two lists, we start by sorting both lists. We are going to step through each item in both lists and compare them. Based on the rules of sorting, an item that appears earlier than another is considered to be "less than". An item that appears later is considered "greater than".

Given lists x and y, and counters i and j where i indicates the current position in x, and j indicates the current position in y - Compare items x[i] and y[j]. If item x[i] is less than y[j] - in other words, appears earlier in sorting - increment _i_by one, which moves our position in x forward. If item y[j] appears earlier in sorting, increase j by one so we move forward in list y. Then compare the two current elements. If the items are the same, copy the current item into our 'shared' list.

The Code Example

You can also grab this code from my Github account.

/**
 * Find shared elements between two lists.
 * @param   {array} x
 * @param   {array} y
 * @returns {[]}
 */
const shared_items = (x, y) => {
  x.sort();
  y.sort();

  let i = 0,
    j = 0;

  const shared = [];

  while (i < x.length && j < y.length) {
    /*
     * If x[i] and y[j] are not equal, Increment
     * the appropriate counter and move on. We can
     * be confident that whichever item is "less than"
     * the other will not appear in the other list later
     * since we sorted the lists before starting the
     * comparison.
     */

    if (x[i] < y[j]) i++;
    else if (y[j] < x[i]) j++;
    /*
     * If x[i] and y[j] are equal,
     * add the shared element to the shared list.
     */ else {
      shared.push(x[i]);
      i++;
      j++;
    }
  }
  return shared;
};

console.log(
  shared_items(
    ["red", "blue", "green", "apple", "cat", "dog"],
    ["purple", "black", "pink", "moose", "cow", "dog", "cat"]
  )
);

You can grab the code from my Github repository for the 30 Days of Algorithms series. Feel free to leave feedback or ask questions in the comments below, or reach me via the Contact Page.