I implemented the Largest Triple Products algorithm, but I use sort which makes my time complexity O(nlogn). Is there a way to implement it without a temporary sorted array?

The problem: You're given a list of n integers arr[0..(n-1)]. You must compute a list output[0..(n-1)] such that, for each index i (between 0 and n-1, inclusive), output[i] is equal to the product of the three largest elements out of arr[0..i] (or equal to -1 if i < 2, as arr[0..i] then includes fewer than three elements). Note that the three largest elements used to form any product may have the same values as one another, but they must be at different indices in arr.

Example:

var arr_2 = [2, 4, 7, 1, 5, 3];
var expected_2 = [-1, -1, 56, 56, 140, 140];

My solution:

function findMaxProduct(arr) {
  // Write your code here
  if(!arr || arr.length === 0)  return [];
  
  let helper = arr.slice();
  helper.sort((a,b)=>a-b);   // THIS IS THE SORT
  
  let ans = [];
  let prod = 1;
  for(let i=0; i<arr.length; i++) {
    if(i < 2) {
      prod *= arr[i];
      ans.push(-1);
    }
    else {
      if(i === 3) {
        prod *= arr[i];
        ans.push(prod);
      } else if(arr[i] < helper[0]) {
        ans.push(prod);
      } else {
        const min = helper.shift();
        prod /= min;
        prod *= arr[i];
        ans.push(prod);
      }
    }
  }
  
  return ans;
}

I implemented the Largest Triple Products algorithm, but I use sort which makes my time complexity \$O(n *log(n))\$. Is there a way to implement it without a temporary sorted array?

The problem:

You're given a list of \$n\$ integers \$arr[0..(n-1)]\$. You must compute a list output \$[0..(n-1)]\$ such that, for each index \$i\$ (between 0 and \$n-1\$, inclusive), \$output[i]\$ is equal to the product of the three largest elements out of \$arr[0..i]\$ (or equal to -1 if \$i < 2\$, as \$arr[0..i]\$ then includes fewer than three elements).

Note that the three largest elements used to form any product may have the same values as one another, but they must be at different indices in arr.

Example:

var arr_2 = [2, 4, 7, 1, 5, 3];
var expected_2 = [-1, -1, 56, 56, 140, 140];

My solution:

function findMaxProduct(arr) {
  // Write your code here
  if(!arr || arr.length === 0)  return [];
  
  let helper = arr.slice();
  helper.sort((a,b)=>a-b);   // THIS IS THE SORT
  
  let ans = [];
  let prod = 1;
  for(let i=0; i<arr.length; i++) {
    if(i < 2) {
      prod *= arr[i];
      ans.push(-1);
    }
    else {
      if(i === 3) {
        prod *= arr[i];
        ans.push(prod);
      } else if(arr[i] < helper[0]) {
        ans.push(prod);
      } else {
        const min = helper.shift();
        prod /= min;
        prod *= arr[i];
        ans.push(prod);
      }
    }
  }
  
  return ans;
}

I implemented the Largest Triple Products algorithm, but I use sort which makes my time complexity O(nlogn). Is there a way to implement it without a temporary sorted array?

The problem: You're given a list of n integers arr[0..(n-1)]. You must compute a list output[0..(n-1)] such that, for each index i (between 0 and n-1, inclusive), output[i] is equal to the product of the three largest elements out of arr[0..i] (or equal to -1 if i < 2, as arr[0..i] then includes fewer than three elements). Note that the three largest elements used to form any product may have the same values as one another, but they must be at different indices in arr.

Example:

var arr_2 = [2, 4, 7, 1, 5, 3];
var expected_2 = [-1, -1, 56, 56, 140, 140];

My solution:

function findMaxProduct(arr) {
  // Write your code here
  if(!arr || arr.length === 0)  return [];
  
  let helper = arr.slice();
  helper.sort((a,b)=>a-b);   // THIS IS THE SORT
  
  let ans = [];
  let prod = 1;
  for(let i=0; i<arr.length; i++) {
    if(i < 2) {
      prod *= arr[i];
      ans.push(-1);
    }
    else {
      if(i === 3) {
        prod *= arr[i];
        ans.push(prod);
      } else if(arr[i] < helper[0]) {
        ans.push(prod);
      } else {
        const min = helper.shift();
        prod /= min;
        prod *= arr[i];
        ans.push(prod);
      }
    }
  }
  
  return ans;
}

Thanks

I implemented the Largest Triple Products algorithm, but I use sort which makes my time complexity O(nlogn). Is there a way to implement it without a temporary sorted array?

The problem: You're given a list of n integers arr[0..(n-1)]. You must compute a list output[0..(n-1)] such that, for each index i (between 0 and n-1, inclusive), output[i] is equal to the product of the three largest elements out of arr[0..i] (or equal to -1 if i < 2, as arr[0..i] then includes fewer than three elements). Note that the three largest elements used to form any product may have the same values as one another, but they must be at different indices in arr.

Example:

var arr_2 = [2, 4, 7, 1, 5, 3];
var expected_2 = [-1, -1, 56, 56, 140, 140];

My solution:

function findMaxProduct(arr) {
  // Write your code here
  if(!arr || arr.length === 0)  return [];
  
  let helper = arr.slice();
  helper.sort((a,b)=>a-b);   // THIS IS THE SORT
  
  let ans = [];
  let prod = 1;
  for(let i=0; i<arr.length; i++) {
    if(i < 2) {
      prod *= arr[i];
      ans.push(-1);
    }
    else {
      if(i === 3) {
        prod *= arr[i];
        ans.push(prod);
      } else if(arr[i] < helper[0]) {
        ans.push(prod);
      } else {
        const min = helper.shift();
        prod /= min;
        prod *= arr[i];
        ans.push(prod);
      }
    }
  }
  
  return ans;
}