Largest Triple Products without using sort?

Question

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

Answer 1

You don't need to sort it. You just maintain an array of the largest three elements at each index.

For the first three elements it is simple you just assign the product of them to the third element in the result.

For the next elements, you add the current element to the three-largest-element-array and sort it and take the elements from 1 to 3 ( the largest three ) and assign the product of those at that index in result array. Then update the three-element-array with largest three.

• Complexity :

This sort and slice of three-element-array should be O(1) because each time atmost 4 elements are there in the array.

Overall complexity is O(n).

You can do it as follows :

function findMaxProduct(arr) {
  if(!arr)  return [];
  if (arr.length < 3) return arr.slice().fill(-1)
  let t = arr.slice(0,3)
  let ans = arr.slice().fill(-1,0,2) //fill first two with -1
  ans[2] = t[0]*t[1]*t[2];
  for(let i=3; i<arr.length; i++) {
    t.push(arr[i]);
    t = t.sort().slice(1,4);
    ans[i] = t[0]*t[1]*t[2];
  }
  return ans;
}

Answer 2

I am keeping the array ordered (manually). Then just get the first 3 elements.

function findMaxProduct(arr) {
  let results = [];
  let heap = [];

  for (let i = 0; i < arr.length; i++) {

    // Insert the new element in the correct position
    for (let j = 0; j < heap.length; j++) {
      if (arr[i] >= heap[j]) {
        heap.splice(j, 0, arr[i]);
        break;
      }
    }

    // No position found, insert at the end
    if (heap.length != i + 1) {
      heap.push(arr[i]);
    }

    if (i < 2) {
      results.push(-1);
    } else {
      results.push(heap[0] * heap[1] * heap[2]);
    }
  }

  return results;
}