Product of Array Except Self

PROBLEM

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1

**Input**: nums = [1,2,3,4]
**Output**: [24,12,8,6]

Example 2

**Input**: nums = [-1,1,0,-3,3]
**Output**: [0,0,9,0,0]

SOLVING

We are going to make to iteration.

• The first one to fill the result by the prefix of each num.
• The second to complete result by the postfix of each num.

Steps

• Create the array result, the same size as nums and fill by 1.
• First iteration from the second element to the end:
  1. result of i equal to nums of i-1 multiply by result of i-1.
• Now we have the result array filled by the suffix of each number.
• Create a temp var prev which will store previous element multiply by it’s previous one. Initial value is 1 because last element has no suffix.
• Second iteration from the end to the beginning:
  1. result of i equal to itself multiply by prev
  2. prev equal to itself multiply by nums of i
• Return result.

Example

• First Iteration

  At the end of the first iteration result will be filled by the suffix of each number

  nums   = [1,2,3,4]
  result = [1,1,1,1]
  i      =    1
  
  (i-1)
   ↓
  [1,2,3,4]
  (i-1)
   ↓
  [1,1,1,1]
  result[i] = nums[i-1] * result[i-1]
  result[1] = 1 * 1
  
     ↓
  [1,2,3,4]
     ↓
  [1,1,1,1]
  result[2] = 2 * 1
  
       ↓
  [1,2,3,4]
       ↓
  [1,1,2,1]
  result[3] = 3 * 2
  
  
  result = [1,1,2,6]
  

• Second Iteration

  nums   = [1,2,3,4]
  result = [1,1,2,6]
  prev   =     1
  
         i
         ↓
  [1,2,3,4]
         i
         ↓
  [1,1,2,6]
  result[i] = result[i] * prev
  prev = prev * nums[i]
  
  result[3] = 6 * 1
  prev = 4  = 1 * 4
  
       ↓
  [1,2,3,4]
       ↓
  [1,1,2,6]
  result[2] = 2 * 4
  prev = 12 = 4 * 3
  
     ↓
  [1,2,3,4]
     ↓
  [1,1,8,6]
  result[1] = 1 * 12
  prev = 24 = 12 * 2
  
   ↓
  [1,2,3,4]
   ↓
  [1,12,8,6]
  result[1] = 1 * 24
  
  result = [24,12,8,6]
  

Code

class Solution {
public:
  vector<int> productExceptSelf(vector<int> &nums) {
    int size = nums.size();
    vector<int> result(size, 1);

    // First iteration
    for (int i = 1; i < size; i++)
      result[i] = result[i - 1] * nums[i - 1];

    int prev = nums[size - 1];
    // Second iteration
    for (int i = size - 2; i >= 0; i--) {
      result[i] *= prev;
      prev *= nums[i];
    }
    return result;
  }
};

• PROBLEM