How to do the product trick on a array

The problem is: given an array of numbers, replace each number with the product of all numbers except itself, without using the divide operator "/".
Quite tricky. Of course the goal is to make the program as fast as possible.

First solution: O(n²) - having a temporary array, iterate through the array. At each iteration, iterate again through the array, skipping the current number and keeping the rest of the product in the temporary array. Kids stuff.

Second solution: O(n) - having two temporary arrays, iterate once through the array and keep the product of all numbers smaller (in index) than the current number. Iterate again in reverse and keep a product of all the numbers bigger (in index) than the current number. At the end, the answer is the product of these two vectors. Example:

   1:  array :  1  2  3  4

   2:  left  :  1  1  2  6 <--at each index is the product of all the previous numbers

   3:  rights: 24 12  4  1 <--at each index is the product of all the next numbers

   4:  final : 24 12  8  6 <--left[0]*right[0], left[1]*right[1]... etc.

The program is equally simple:

   1:  void product(int* vec, int size) {

   2:      int* left = new int[size]; //left products

   3:      int* right = new int[size]; //right products

   4:      int product = 1;

   5:      left[0] = 1;

   6:      right[size - 1] = 1;

   7:      for (int i = 1; i < size; i++) {

   8:          left[i] = product * vec[i - 1];//keep the product of prev numbers

   9:          product = left[i];

  10:      }

  11:      product = 1;

  12:      for (int i = size - 2; i >= 0; i--) {

  13:          right[i] = product * vec[i + 1];//keep the product of next numbers

  14:          product = right[i];

  15:      }

  16:      for (int i = 0; i < size; i++)

  17:          vec[i] = left[i] * right[i]; // compute the final results

  18:      delete[] left;

  19:      delete[] right;

  20:  }