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

You can make an array that holds three currently largest integers, and update that array as you passing through original array. That's how you will always have three currently largest numbers and you will be able to solve this with O(n) time complexity.

Answer 3

I think there's a faster and more efficient way to go about this. This is a similar thought process as @Q2Learn, using Python; just faster:

def findMaxProduct(arr):
 
  #create a copy of arr
    
  solution = arr.copy()
  # make first 2 elements -1
  for i in range(0,2):
    solution[i] = -1
    
#for each item in copy starting from index 2, multiply  item from 2 indices b'4 (notice how each index of arr being multiplied is reduced by 2, 1 and then 0, to accommodate each move)
  
  for i in range(2, len(arr)):
    solution[i] = arr[i-2] * arr[i-1] * arr[i]
  return solution

check = findMaxProduct(arr)
print(check)

Answer 4

    public int[] LargestTripleProducts(int[] input)
    {
        var ansArr = new int[input.Length];
        var firstLargetst = input[0];
        var secondLargetst = input[1];
        ansArr[0] = ansArr[1] = -1;
        for (int i = 2; i < input.Length; i++)
        {
            ansArr[i] = firstLargetst * secondLargetst * input[i];
            if (firstLargetst < input[i] && firstLargetst < secondLargetst)
            {
                firstLargetst= input[i];
                continue;
            }
            if (secondLargetst < input[i] && secondLargetst < firstLargetst)
            {
                secondLargetst= input[i]; 
            }
        }
        return ansArr;
    }
    

Answer 5

Python solution based on @SomeDude answer above. See explanation there.

def findMaxProduct(arr):

  if not arr:
    return None
  
  if len(arr) < 3:
    for i in range(len(arr)):
      arr[i] = -1
    return arr
  
  three_largest_elem = arr[0:3]
  answer = arr.copy()
  
  for i in range(0, 2):
    answer[i] = -1
  
  answer[2] = three_largest_elem[0] * three_largest_elem[1] * three_largest_elem[2]
  
  for i in range(3, len(arr)):
    
    three_largest_elem.append(arr[i])
    three_largest_elem = sorted(three_largest_elem)
    three_largest_elem = three_largest_elem[1:4]
    
    answer[i] = three_largest_elem[0] * three_largest_elem[1] * three_largest_elem[2]
    
  return answer #Time: O(1) n <= 4, to Overall O(n) | Space: O(1)

Answer 6

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

Answer 7

Python has it's in-built package heapq, look at it for it.

Credit: Martin

> Helper function for any type of calculations
import math

> Heap algorithm
import heapq

> Create empty list to append output values
output = [] 

def findMaxProduct(arr):

  out = []
  h = []
  
  for e in arr:
    heapq.heappush(h, e)
    if len(h) < 3:
      out.append(-1)
    else:
      if len(h) > 3:
        heapq.heappop(h)
      out.append(h[0] * h[1] * h[2])
  
  return out

Hope this helps!

Answer 8

Single Scan Algorithm O(n)

We don't need to necessarily sort the given array to find the maximum product. Instead, we can only find the three largest values (x, y, z) in the given stage of iteration:

JavaScript:

function findMaxProduct(arr) {
  let reults = []
  let x = 0
  let y = 0
  let z = 0
  for(let i=0; i<arr.length; i++) {
    n = arr[i]
    if (n > x) {
        z = y
        y = x
        x = n
    }
    if (n < x && n > y) {
        z = y
        y = n
    }
    if (n < y && n > z) {
        z = n
    }
    ans = x*y*z
    if (ans === 0) {
        results.push(-1)
    } else {
        results.push(ans)
    }
  return ans;
}

Python:

def findMaxProduct(arr):
    results = []
    if not arr:
        return []
    x = 0
    y = 0
    z = 0
    for i, n in enumerate(arr):
        if n > x:
            z = y
            y = x
            x = n
        if n < x and n > y:
            z = y
            y = n
        if n < y and n > z:
            z = n
        ans = x*y*z
        if ans == 0:
            results.append(-1)
        else:
            results.append(ans)

    print(results)