Find the maximum sum of products of two arrays.

We will implement a simple algorithm in Javascript to find the maximum sum of products of given twoarrays. Both the arrays will be of the same length.

Example

Input:
[1, 2, 3]
[5, 4, 3]

[4, 7, 5, 2]
[2, 3, 2 ,1]

Output:
26 = 5 * 3 + 4 * 2 + 3 * 1
41 = 7 * 3 + 5 * 2 + 4 * 2 + 2 * 1

Implementation

  • We will first sort both the arrays in any order.
  • Then we will find the product of the each elements and add them.
  • Everything will be written in ES6.
let productSum = (arr1, arr2) => {
  //sort the arrays in ascending order
  arr1.sort();
  arr2.sort();
  
  let sum = 0;

  //calculate the sum of the products
  for(let i = 0; i < arr1.length; i++){
    sum += arr1[i] * arr2[i];
  }
  
  return sum;
}
Input:
console.log(productSum([1, 2, 3], [5, 4, 3]));
console.log(productSum([4, 7, 5, 2], [2, 3, 2 ,1]));

Output:
26
41

Time complexity: O(nlogn)

Space complexity: O(1)

Time and Space complexity

  • We are sorting both the arrays which will take O(nlogn) then we are calculating the sum of the products of each element which will take O(n), so Time complexity is O(nlogn).
  • We are using constant space, so Space complexity is O(n).

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *