Largest Triple Products without using sort?

Question

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;
}

Answer 1

Comments should be crisp and express intent that can't otherwise be stated clearly and/or concisely in the implementation. Your code has artifacts and redundant commentary.

  // Write your code here

  helper.sort((a,b)=>a-b);   // THIS IS THE SORT

---

Explicitly handle conditional expressions. By explicitly defining the condition, you reduce the chance of unexpected behavior from automatic type coercion.

Use braces for single-statement blocks. Braces make it clear which block is bound to a conditional statement.

    if (!Array.isArray(arr) || arr.length === 0) {
      return [];
    }

---

Be consistent with your formatting.

      if(i < 2) {
        ...
      }
      else {
        if(i === 3) {
          ...
        } else if(arr[i] < helper[0]) {
          ...
        } else {
          ...
        }
      }

The outer if-else uses the Stroustrup variant of K&R.

  if (...) {
    ...
  }
  else {
    ...
  }

The inner if-else if-else uses the One True Brace Style variant of K&R.

  if (...) {
    ...
  } else {
    ...
  }

Pick one. Even better, use a code formatter/linter to apply a consistent style for your code.

---

    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);
        }

The initial if blocks in the loop are only taken the first, second, and fourth iterations (third iteration instead of fourth when fixed, see next point). You can extract these operations and have them occur before entering the loop.

  function findMaxProduct(inputArray) {
    let result = new Array(inputArray?.length ?? 0).fill(-1, 0, 2);
    if (result.length < 2) {
      return result;
    }

    const multiply = (a, b) => a * b;
    
    let top3 = inputArray.slice(0, 3).sort();
    result[2] = top3.reduce(multiply, 1);

    for (let i = 3; i < inputArray.length; ++i) {
      if (inputArray[i] <= top3[0]) {
        result[i] = result[i - 1];
        continue;
      }
      
      top3[0] = inputArray[i];
      result[i] = top3.sort().reduce(multiply, 1);
    }

    return result;
  }

---

Test your code. While this post is on topic because it meets the minimum requirements of "running to the best of your knowledge", you need to test beyond the example provided. Testing would have shown basic errors.

1. i === 3 should be i === 2. Seems like you've mixed up length and index.
2. Your use of helper as a min stack doesn't work outside of specific inputs. Consider the sequence [6, 5, 4, 3, 2] with an expected output of [-1, -1, 120, 120, 120]. Your program gives [-1, -1, 60, 180, 180] or [-1, -1, 120, 180, 180] if you fix the previous point.
3. If the sequence contains 0, the first time you divide by 0 will cause prod to get stuck at infinity.

Answer 2

Nested conditionals

There are times it makes sense to nest conditionals, but in the case of your code, it's unnecessary.

This:

    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);
      }
    }

Is better written:

    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);
    }

Answer 3

Hmm, apparently OP has done this - although the problem statement did not suggest it.

---

Is there a way to implement it without a temporary sorted array?

Yes - at least not a sorted array of size n, but of size 3.

A single pass through the list only needs to keep track of the 3 largest prior values. So we still have a sorted array of 3.

// Pseudo code
Fill max_list[3] with sorted first 3 array elements.
product = max_list[0] * max_list[1] * max_list[2]
for (i = 3; i < n; i++) {
  if (list[i] > max_list[0]) {
    max_list[0] = list[i]
    sort_list low to high // Perhaps bubble sort here.
    form product
  }
  output product to expected array
}


  

Complexity: O(n).

---

OP mentions value are non-negative. Even with negatives only short lists are needed.