/**
 * Idea behind this problem is using rolling product from left to right and right to left, and
 * merging two sequences together, e.g. for array [3, 4, 5, 6], you will have 2 sequences:
 * left -> right
 * [3, 12, 60, 360]
 * right -> left
 * [360, 120, 30, 6]
 * Resulting array is constructed as follows: each element at index i is a product of
 * left->right[i - 1] and right->left[i + 1]; essentially excluding ith element. For corner cases
 * we just take whatever array is relevant, e.g. for 0 index we look at right->left[1] element and
 * vice versa. This solution requires O(2*n) => O(n) space complexity.
 *
 * We can observe that container arrays are not necessary, because we can use resulting array as a
 * container. We put rolling product (either left -> right or right -> left, does not really matter)
 * first into resulting array, and then we iterate backwards and treat i-1 index as element from
 * opposite container.
 *
 * See steps code for explanation how we come to the solution below.
 */
public class Solution {
  // final solution, runs in O(1) space complexity and O(n) time complexity
  public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];

    // Bulding rolling product left -> right
    int product = 1;
    for (int i = 0; i < n; i++) {
      res[i] = product * nums[i];
      product *= nums[i];
    }

    // Going in opposite direction and using previous element in `res` as left[i - 1]
    // and `product` as right[i + 1]
    product = 1;
    for (int i = n - 1; i > 0; i--) {
      res[i] = res[i - 1] * product;
      product *= nums[i];
    }
    res[0] = product;

    return res;
  }
}

// Improvement 1: using 2 arrays as containers for rolling products (left, right)
public class Solution {
  public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    int[] left = new int[n];
    int[] right = new int[n];

    for (int i = 0; i < n; i++) {
      int k = (i == 0) ? 1 : left[i - 1];
      left[i] = k * nums[i];
    }

    for (int i = n - 1; i >= 0; i--) {
      int k = (i == n - 1) ? 1 : right[i + 1];
      right[i] = k * nums[i];
    }

    for (int i = 0; i < n; i++) {
      if (i == 0) {
        res[i] = right[i + 1];
      } else if (i == n - 1) {
        res[i] = left[i - 1];
      } else {
        res[i] = left[i - 1] * right[i + 1];
      }
    }

    return res;
  }
}

// Improvement 2: Realising that one of the containers is not neccessary and can be replaced with
// resulting array. Still using one container. See actual solution above for removing container and
// storing everything in resulting array.
public class Solution {
  public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    int[] left = new int[n];

    for (int i = 0; i < n; i++) {
      int k = (i == 0) ? 1 : left[i - 1];
      left[i] = k * nums[i];
    }

    int right = 1;
    for (int i = n - 1; i > 0; i--) {
      res[i] = left[i - 1] * right;
      right *= nums[i];
    }
    res[0] = right;

    return res;
  }
}

@@ -1046,16 +1046,21 @@
 / final 
+fast 
 solution
@@ -1090,16 +1090,32 @@
 mplexity
+ (without %60out%60)
  and O(n
@@ -1132,16 +1132,68 @@
 plexity%0A
+  // works on empty arrays and arrays of 1 element.%0A
   public
@@ -1230,37 +1230,49 @@
  nums) %7B%0A    int
- n = 
+%5B%5D out = new int%5B
 nums.length;%0A   
@@ -1258,32 +1258,33 @@
  int%5Bnums.length
+%5D
 ;%0A    int%5B%5D res 
@@ -1280,171 +1280,144 @@
  int
-%5B%5D res = new int%5Bn%5D;%0A%0A    // Bulding rolling product left -%3E right%0A    int product = 1;%0A    for (int i = 0; i %3C n; i++) %7B%0A      res%5Bi%5D = product * nums%5Bi%5D;
+ p = 1; // assume product does not overflow%0A    for (int i = 0; i %3C nums.length; i++) %7B // Bulding rolling product left -%3E right
 %0A      p
 rodu
@@ -1404,38 +1404,32 @@
 -%3E right%0A      p
-roduct
  *= nums%5Bi%5D;%0A   
@@ -1433,150 +1433,73 @@
     
-%7D%0A%0A    // Going in opposite direction and using previous element in %60res%60 as left%5Bi - 1%5D%0A    // and %60product%60 as right%5Bi + 1%5D%0A    product = 1;
+  out%5Bi%5D = p;%0A    %7D%0A    p = 1; // reset to use from right to left
 %0A   
@@ -1505,32 +1505,42 @@
   for (int i = n
+ums.length
  - 1; i %3E 0; i--
@@ -1524,32 +1524,33 @@
 .length - 1; i %3E
+=
  0; i--) %7B%0A     
@@ -1554,20 +1554,34 @@
     
-res
+out
 %5Bi%5D = 
-res
+i == 0 ? p : (out
 %5Bi -
@@ -1587,22 +1587,17 @@
 - 1%5D * p
-roduct
+)
 ;%0A      
@@ -1597,22 +1597,16 @@
 %0A      p
-roduct
  *= nums
@@ -1620,31 +1620,8 @@
   %7D%0A
-    res%5B0%5D = product;%0A%0A
     
@@ -1619,35 +1619,35 @@
    %7D%0A    return 
-res
+out
 ;%0A  %7D%0A%7D%0A%0A// Impr

update solution