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.

1	int[] findMaxProduct(int[] arr)

int[] findMaxProduct(int[] arr)

Input
n is in the range [1, 100,000].
Each value arr[i] is in the range [1, 1,000].

Output
Return a list of n integers output[0..(n-1)], as described above.

Example 1
n = 5
arr = [1, 2, 3, 4, 5]
output = [-1, -1, 6, 24, 60]
The 3rd element of output is 3*2*1 = 6, the 4th is 4*3*2 = 24, and the 5th is 5*4*3 = 60.

Example 2
n = 5
arr = [2, 1, 2, 1, 2]
output = [-1, -1, 4, 4, 8]
The 3rd element of output is 2*2*1 = 4, the 4th is 2*2*1 = 4, and the 5th is 2*2*2 = 8.

Largest Triple Products by Sorting 3 Elements

We can keep an array of maximum 3 numbers. For each iteration, we push the current number and sort the array, then pop the smallest number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

vector<int> findMaxProduct(const vector<int> &arr) {
  vector<int> ans(arr.size(), -1);
  vector<int> max3 = {arr[0], arr[1]};
  for (int i = 2; i < arr.size(); ++ i) {
    max3.push_back(arr[i]);
    if (max3.size() > 3) {
      sort(begin(max3), end(max3), [](auto &a, auto &b) {
        return b < a;
      });
      max3.pop_back();
    }
    ans[i] = max3[0] * max3[1] * max3[2];
  }
  return ans;
}

vector<int> findMaxProduct(const vector<int> &arr) {
  vector<int> ans(arr.size(), -1);
  vector<int> max3 = {arr[0], arr[1]};
  for (int i = 2; i < arr.size(); ++ i) {
    max3.push_back(arr[i]);
    if (max3.size() > 3) {
      sort(begin(max3), end(max3), [](auto &a, auto &b) {
        return b < a;
      });
      max3.pop_back();
    }
    ans[i] = max3[0] * max3[1] * max3[2];
  }
  return ans;
}

The time complexity is O(N) although we are using sort process in the loop – but the complexity for sorting the 4 numbers is constant.

We can remove the condition check in the loop – the first triple products can be computed directly without sorting:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

vector<int> findMaxProduct(const vector<int> &arr) {
  vector<int> ans(arr.size(), -1);
  vector<int> max3 = {arr[0], arr[1], arr[2]};
  ans[2] = arr[0] * arr[1] * arr[2];
  for (int i = 3; i < arr.size(); ++ i) {
    max3.push_back(arr[i]);
    sort(begin(max3), end(max3), [](auto &a, auto &b) {
      return b < a;
    });
    max3.pop_back();
    ans[i] = max3[0] * max3[1] * max3[2];
  }
  return ans;
}

vector<int> findMaxProduct(const vector<int> &arr) {
  vector<int> ans(arr.size(), -1);
  vector<int> max3 = {arr[0], arr[1], arr[2]};
  ans[2] = arr[0] * arr[1] * arr[2];
  for (int i = 3; i < arr.size(); ++ i) {
    max3.push_back(arr[i]);
    sort(begin(max3), end(max3), [](auto &a, auto &b) {
      return b < a;
    });
    max3.pop_back();
    ans[i] = max3[0] * max3[1] * max3[2];
  }
  return ans;
}

This algorithm is correct because the large elements stay once they come in (they are not discarded) – therefore we just need to keep the maximum 3 numbers at any time.

You can also use Priority queue to pop 3 numbers.

–EOF (The Ultimate Computing & Technology Blog) —