The Cartesian Product algorithm is a very interesting question that you may have heard in your school or college asked in many interviews including FAANG companies.  


In set theory, a Cartesian product is a mathematical operation that returns a set (or product set or simply product) from multiple sets. That is, for sets A and B, the Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.


Cartesian product AxB of two sets A={x,y,z} and B={1,2,3}


Example 1:

Input: SetA = ['x','y','z'], SetB = [1,2,3]

Output: [['x',1],['x',2],['x',3],['y',1],['y',2],['y',3],['z',1],['z',2],['z',3]]


Example 2:

Input: SetA = [3,2,1], SetB = [1,2,3]

Output: [[3,1],[3,2],[3,3],[2,1],[2,2],[2,3],[1,1],[1,2],[1,3]]


Let's start with the algorithm,


var cartesianProduct = function(setA, setB) {

  // Check if input sets are not empty.

  // Otherwise return null since we can't generate Cartesian Product out of them.

  if (!setA || !setB || !setA.length || !setB.length) {

    return null;

  }

  // Init product set.

  const product = [];

  // Now, let's go through all elements of a first and second set and form all possible pairs.

  for (let indexA = 0; indexA < setA.length; indexA ++) {

    for (let indexB = 0; indexB < setB.length; indexB ++) {

      // Add current product pair to the product set.

      product.push([setA[indexA], setB[indexB]]);

    }

  }

  // Return cartesian product set.

  return product;

}



I hope you understood the algorithm. If you have any doubts, please let us know in the comments.